stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



	for(int i = 0; i < n; i++){

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

	for(int i = 0; i < n; i++){

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[i]] + v[i]);

		}

	}



	ll ans = 0;

	for(int i = 0; i <= w; i++) ans = max(ans, dp[i]);



	cout <<ans <<endl;

    	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.2665537411583423x):
#include<bits/stdc++.h>

#define ll long long

#define fi first

#define se second

using namespace std;

typedef pair<ll,ll> lp;

const int inf=0x3f3f3f3f;

void A() {

    int n;

    cin>>n;

    vector<int> a(n,0);

    for(int i=0; i<n; i++)

        cin>>a[i];

    vector<int> dp(n+1,inf);

    dp[0]=0;

    for(int i=1; i<n; i++) {

        dp[i]=min(dp[i],dp[i-1]+abs(a[i]-a[i-1]));

        if(i>=2)

            dp[i]=min(dp[i],dp[i-2]+abs(a[i]-a[i-2]));

    }

    cout<<dp[n-1]<<endl;



}

void B() {

    int n,k;

    cin>>n>>k;

    vector<int> dp(n+1,inf);

    vector<int> h(n,0);

    for(int i=0; i<n; i++)

        cin>>h[i];

    dp[0]=0;

    for(int i=1; i<n; i++) {

        for(int len=1; len<=min(k+1,i+1); len++) {

            int j=i-len+1;

            dp[i]=min(dp[i],dp[j]+abs(h[j]-h[i]));

        }

    }

    cout<<dp[n-1]<<endl;

}

void C() {

    int n;

    cin>>n;

    vector<vector<int>> a(n,vector<int>(3,0));

    for(int i=0;i<n;i++) cin>>a[i][0]>>a[i][1]>>a[i][2];

    vector<vector<int>> dp(n,vector<int>(3,0));

    dp[0][0]=a[0][0];

    dp[0][1]=a[0][1];

    dp[0][2]=a[0][2];

    for(int i=1; i<n; i++) {

        for(int j=0; j<3; j++) {

            for(int k=0; k<3; k++) {

                if(j==k)

                    continue;

                dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);

                //cout<<dp[i][j]<<endl;

            }

        }

    }

    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;

}

void D()

{

    ll n,W;

    cin>>n>>W;

    vector<lp> p;

    for(int i=0;i<n;i++){

        ll a,b;

        cin>>a>>b;

        p.emplace_back(a,b);

    }

    sort(p.begin(),p.end());

    vector<ll> dp(W+1,0);

    for(int i=0;i<n;i++){

        for(int j=W;j>=p[i].first;j--){

            if(j>0) dp[j]=max(dp[j],dp[j-1]);

            dp[j]=max(dp[j],dp[j-p[i].fi]+p[i].se);

        }

    }

    cout<<dp[W]<<endl;



}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);

    D();

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



	for(int i = 0; i < n; i++){

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

	for(int i = 0; i < n; i++){

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[i]] + v[i]);

		}

	}



	ll ans = 0;

	for(int i = 0; i <= w; i++) ans = max(ans, dp[i]);



	cout <<ans <<endl;

    	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.3140378486422497x):
#include <iostream>

using namespace std;

#define ll long long int

ll knapSack(ll W, int w[], int v[], int n) {

   ll i, wt;

   ll K[n + 1][W + 1];

   for (i = 0; i <= n; i++) {

      for (wt = 0; wt <= W; wt++) {

         if (i == 0 || wt == 0)

         K[i][wt] = 0;

         else if (w[i - 1] <= wt)

            K[i][wt] = max(v[i - 1] + K[i - 1][wt - w[i - 1]], K[i - 1][wt]);

         else

        K[i][wt] = K[i - 1][wt];

      }

   }

   return K[n][W];

}

int main() {

  

   long long int n, W;

   cin >> n>>W;

   int v[n], w[n];

   for (int i = 0; i < n; i++) {

      cin >> w[i];

	  cin >> v[i];

      

   }

   cout << knapSack(W, w, v, n);

   return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



	for(int i = 0; i < n; i++){

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

	for(int i = 0; i < n; i++){

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[i]] + v[i]);

		}

	}



	ll ans = 0;

	for(int i = 0; i <= w; i++) ans = max(ans, dp[i]);



	cout <<ans <<endl;

    	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.289563029226874x):
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

using namespace std;



#define all(a)                      a.begin(), a.end()

#define pb                          push_back

#define ll							long long

#define index(a)            		order_of_key(a)

#define value(a)					find_by_order(a)

#define count_1 					__builtin_popcount

#define mod(x, m)					((((x) % (m)) + (m)) % (m))

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;



ll dp[101][100005], w[100005], c[100005];



int main() {

	ios_base::sync_with_stdio(0); cin.tie(0); cout << setprecision(12);



	ll n, C;

	cin >> n >> C;

	for (int i = 1; i <= n; i++) {

		cin >> w[i] >> c[i];

	}



	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= C; j++) {

			if (j < w[i])

				dp[i][j] = dp[i - 1][j];

			else

				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);

		}

	}

	cout << dp[n][C];

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



	for(int i = 0; i < n; i++){

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

	for(int i = 0; i < n; i++){

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[i]] + v[i]);

		}

	}



	ll ans = 0;

	for(int i = 0; i <= w; i++) ans = max(ans, dp[i]);



	cout <<ans <<endl;

    	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.3452717494549633x):
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100

#define MAXW 100000

#define INF 2000000000





int w[MAXN], v[MAXN];

int n,C;

long long dp[MAXN+1][MAXW+1];





int main() {

	int i,j;

	scanf("%d %d",&n, &C);	

	for (i=0; i<n;i++) {

		scanf("%d %d",&w[i],&v[i]);

	}

	//for (i=0; i<=n;i++) {

		for (j=0; j<=C; j++) {

			dp[n][j]=0;

		}

	//}

	for (i=n-1; i>=0; i--) {

		for (j=0; j<=C; j++) {

			dp[i][j]=dp[i+1][j];

			if (j-w[i]>=0) {

				dp[i][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);

			}

		}

	}



	printf("%lld\n",dp[0][C]);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



	for(int i = 0; i < n; i++){

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

	for(int i = 0; i < n; i++){

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[i]] + v[i]);

		}

	}



	ll ans = 0;

	for(int i = 0; i <= w; i++) ans = max(ans, dp[i]);



	cout <<ans <<endl;

    	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.31524483479118x):
#include <bits/stdc++.h>

using namespace std;



#define ll long long int

#define oo (1L<<62)



int Items, Cap;

ll memo [105][100005];

int v[105];

int p[105];



ll mochila(int item, int cap){

	if(cap<0) return -oo;

	if(!cap || item == -1) return 0;

	if(memo[item][cap]) return memo[item][cap];

	return memo[item][cap] = max(mochila(item-1, cap),

								v[item]+mochila(item-1, cap-p[item]));

}



int main() {

	cin>>Items>>Cap;

	for(int i = 0; i<Items; i++)

		cin>>p[i]>>v[i];

	cout<<mochila(Items-1, Cap)<<"\n";

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



	for(int i = 0; i < n; i++){

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

	for(int i = 0; i < n; i++){

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[i]] + v[i]);

		}

	}



	ll ans = 0;

	for(int i = 0; i <= w; i++) ans = max(ans, dp[i]);



	cout <<ans <<endl;

    	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.3457359396224025x):
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100

#define MAXW 100000

#define INF 2000000000



int w[MAXN], v[MAXN];

int n,C;

long long dp[MAXN+1][MAXW+1];



int main() {

	int i,j;

	scanf("%d %d",&n, &C);	

	for (i=0; i<n;i++) {

		scanf("%d %d",&w[i],&v[i]);

	}

	for (i=n-1; i>=0; i--) {

		for (j=0; j<=C; j++) {

			dp[i][j]=dp[i+1][j];

			if (j-w[i]>=0) {

				dp[i][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);

			}

		}

	}

	printf("%lld\n",dp[0][C]);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



	for(int i = 0; i < n; i++){

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

	for(int i = 0; i < n; i++){

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[i]] + v[i]);

		}

	}



	ll ans = 0;

	for(int i = 0; i <= w; i++) ans = max(ans, dp[i]);



	cout <<ans <<endl;

    	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.2672450216090563x):
#include <bits/stdc++.h>

#define endl '\n'

#define ll long long

using namespace std;



const int MXN = 110;

const int MXK = 100005;

int n, k;

int v[MXN], w[MXN];

// ll dp[MXN][MXK];



int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> n >> k;

    for(int i = 1; i <= n; i++) {

        cin >> w[i] >> v[i];

    }

    // for(int i = n - 1; i >= 0; i--) {

    //     for(int j = k; j >= 0; j--) {

    //         dp[i][j] = dp[i + 1][j];

    //         if(j + w[i] <= k) {

    //             dp[i][j] = max(dp[i][j], dp[i + 1][j + w[i]] + v[i]);

    //         }

    //     }

    // }

    // cout << dp[0][0] << endl;

    vector<ll> dp(k + 1, 0);

    for(int i = 1; i <= n; i++) {

        vector<ll> dpt(k + 1, 0);

        for(int j = 0; j <= k; j++) {

            dpt[j] = dp[j];

            if(j - w[i] >= 0) {

                dpt[j] = max(dpt[j], dp[j - w[i]] + v[i]);

            }

        }

        dp = dpt;

    }

    cout << dp[k] << endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



	for(int i = 0; i < n; i++){

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

	for(int i = 0; i < n; i++){

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[i]] + v[i]);

		}

	}



	ll ans = 0;

	for(int i = 0; i <= w; i++) ans = max(ans, dp[i]);



	cout <<ans <<endl;

    	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.2788132718002376x):
#include <bits/stdc++.h>

#define ll long long

using namespace std;

#define inf 0x3f3f3f3f 

int main(){

	ll  n , W; cin >> n >> W;

    ll w[101] , v[101] , dp[100001] = {0};

    for(int i = 0 ; i < n ; ++i)

        cin >> w[i] >> v[i];

    for(int i = 0 ; i < n ; ++i)

        for(int j = W ; j >= w[i] ; j--)

            dp[j] = max(dp[j] , dp[j - w[i]] + v[i]);



    cout<< dp[W] <<endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



	for(int i = 0; i < n; i++){

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

	for(int i = 0; i < n; i++){

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[i]] + v[i]);

		}

	}



	ll ans = 0;

	for(int i = 0; i <= w; i++) ans = max(ans, dp[i]);



	cout <<ans <<endl;

    	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.2858957241423778x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;





ll w[105],f[100005];

ll v[105];



signed main()

{

	ll N,W;

	while(cin>>N>>W){

		for(ll i=1;i<=N;i++)

		cin>>w[i]>>v[i];

		

		//01背包 

		memset(f,0,sizeof f);

		for(ll i=1;i<=N;i++){

			for(ll j=W;j>=w[i];j--)

			f[j]=max(f[j],f[j-w[i]]+v[i]);

		}	

		

		cout<<f[W]<<endl;

	}

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



	for(int i = 0; i < n; i++){

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

	for(int i = 0; i < n; i++){

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[i]] + v[i]);

		}

	}



	ll ans = 0;

	for(int i = 0; i <= w; i++) ans = max(ans, dp[i]);



	cout <<ans <<endl;

    	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.3454003780410506x):
#include <bits/stdc++.h>

using namespace std;

int main()

{

	int n,m;

	scanf("%d %d",&n,&m);

	int a[n+1];

	long long b[n+1];

	for(int i=1;i<=n;i++)

	{

		scanf("%d %lld",&a[i],&b[i]);

	}

	long long v[n+1][m+1];

	for(int i=0;i<m+1;i++)

	{

		for(int t=0;t<n+1;t++)

		{

			v[t][i]=0;

		}

	}

	for(int i=1;i<=n;i++)//从第一件开始循环（这样可以保证每件商品只是用一次） 

	{

		for(int j=1;j<=m;j++)//从最小容纳量开始循环 

		{

			if(j<a[i])

			{

				v[i][j]=v[i-1][j];

			}

			else

			{

				v[i][j]=max(v[i-1][j],v[i-1][j-a[i]]+b[i]);

			}

		}

	}

	long long big=v[0][m];

	for(int i=1;i<=n;i++)

	{

		if(big<v[i][m])big=v[i][m];

	}

	printf("%lld",big);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

using namespace std;

#define inf 0x3f3f3f3f 

int main(){

	ll  n , W; cin >> n >> W;

    ll w[101] , v[101] , dp[100001] = {0};

    for(int i = 0 ; i < n ; ++i)

        cin >> w[i] >> v[i];

    for(int i = 0 ; i < n ; ++i)

        for(int j = W ; j >= w[i] ; j--)

            dp[j] = max(dp[j] , dp[j - w[i]] + v[i]);



    cout<< dp[W] <<endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.8340444455501583x):
#include <bits/stdc++.h>

using namespace std;

int main()

{

	int n,m;

	scanf("%d %d",&n,&m);

	int a[n+1];

	long long b[n+1];

	for(int i=1;i<=n;i++)

	{

		scanf("%d %lld",&a[i],&b[i]);

	}

	long long v[n+1][m+1];

	for(int i=0;i<m+1;i++)

	{

		for(int t=0;t<n+1;t++)

		{

			v[t][i]=0;

		}

	}

	for(int i=1;i<=n;i++)//从第一件开始循环（这样可以保证每件商品只是用一次） 

	{

		for(int j=1;j<=m;j++)//从最小容纳量开始循环 

		{

			if(j<a[i])

			{

				v[i][j]=v[i-1][j];

			}

			else

			{

				v[i][j]=max(v[i-1][j],v[i-1][j-a[i]]+b[i]);

			}

		}

	}

	long long big=v[0][m];

	for(int i=1;i<=n;i++)

	{

		if(big<v[i][m])big=v[i][m];

	}

	printf("%lld",big);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;





ll w[105],f[100005];

ll v[105];



signed main()

{

	ll N,W;

	while(cin>>N>>W){

		for(ll i=1;i<=N;i++)

		cin>>w[i]>>v[i];

		

		//01背包 

		memset(f,0,sizeof f);

		for(ll i=1;i<=N;i++){

			for(ll j=W;j>=w[i];j--)

			f[j]=max(f[j],f[j-w[i]]+v[i]);

		}	

		

		cout<<f[W]<<endl;

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.8239429014396207x):
#include <bits/stdc++.h>

using namespace std;

int main()

{

	int n,m;

	scanf("%d %d",&n,&m);

	int a[n+1];

	long long b[n+1];

	for(int i=1;i<=n;i++)

	{

		scanf("%d %lld",&a[i],&b[i]);

	}

	long long v[n+1][m+1];

	for(int i=0;i<m+1;i++)

	{

		for(int t=0;t<n+1;t++)

		{

			v[t][i]=0;

		}

	}

	for(int i=1;i<=n;i++)//从第一件开始循环（这样可以保证每件商品只是用一次） 

	{

		for(int j=1;j<=m;j++)//从最小容纳量开始循环 

		{

			if(j<a[i])

			{

				v[i][j]=v[i-1][j];

			}

			else

			{

				v[i][j]=max(v[i-1][j],v[i-1][j-a[i]]+b[i]);

			}

		}

	}

	long long big=v[0][m];

	for(int i=1;i<=n;i++)

	{

		if(big<v[i][m])big=v[i][m];

	}

	printf("%lld",big);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



	for(int i = 0; i < n; i++){

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

	for(int i = 0; i < n; i++){

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[i]] + v[i]);

		}

	}



	ll ans = 0;

	for(int i = 0; i <= w; i++) ans = max(ans, dp[i]);



	cout <<ans <<endl;

    	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.316428502421664x):
#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

ll a[105],b[105],dp[100005];

int main()

{

    int n;

    ll w,i,j;

    cin>>n>>w;

    for(i=1;i<=n;i++)

    cin>>a[i]>>b[i];

    for(i=1;i<=n;i++)

    {

    	for(j=w;j>=a[i];j--)

    	{

    		dp[j]=max(dp[j],dp[j-a[i]]+b[i]);

		}

	}

	cout<<dp[w];

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

using namespace std;

#define inf 0x3f3f3f3f 

int main(){

	ll  n , W; cin >> n >> W;

    ll w[101] , v[101] , dp[100001] = {0};

    for(int i = 0 ; i < n ; ++i)

        cin >> w[i] >> v[i];

    for(int i = 0 ; i < n ; ++i)

        for(int j = W ; j >= w[i] ; j--)

            dp[j] = max(dp[j] , dp[j - w[i]] + v[i]);



    cout<< dp[W] <<endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.8113891632988237x):
#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

ll a[105],b[105],dp[100005];

int main()

{

    int n;

    ll w,i,j;

    cin>>n>>w;

    for(i=1;i<=n;i++)

    cin>>a[i]>>b[i];

    for(i=1;i<=n;i++)

    {

    	for(j=w;j>=a[i];j--)

    	{

    		dp[j]=max(dp[j],dp[j-a[i]]+b[i]);

		}

	}

	cout<<dp[w];

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;





ll w[105],f[100005];

ll v[105];



signed main()

{

	ll N,W;

	while(cin>>N>>W){

		for(ll i=1;i<=N;i++)

		cin>>w[i]>>v[i];

		

		//01背包 

		memset(f,0,sizeof f);

		for(ll i=1;i<=N;i++){

			for(ll j=W;j>=w[i];j--)

			f[j]=max(f[j],f[j-w[i]]+v[i]);

		}	

		

		cout<<f[W]<<endl;

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.8014123998791542x):
#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

ll a[105],b[105],dp[100005];

int main()

{

    int n;

    ll w,i,j;

    cin>>n>>w;

    for(i=1;i<=n;i++)

    cin>>a[i]>>b[i];

    for(i=1;i<=n;i++)

    {

    	for(j=w;j>=a[i];j--)

    	{

    		dp[j]=max(dp[j],dp[j-a[i]]+b[i]);

		}

	}

	cout<<dp[w];

	return 0;

}