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.318678281148379x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const int N=105;

const int maxn=1e5+5;

int a[N],v[N];

ll dp[N][maxn];

int main(){

	int n,k;

	cin>>n>>k;

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

		cin>>a[i]>>v[i];

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

		dp[i][0]=0,	dp[0][i]=0;

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

		for(int j=1;j<=k;++j)

			if(j<a[i]) dp[i][j]=dp[i-1][j];

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

		cout<<dp[n][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: 2.346532121841585x):
#include<bits/stdc++.h>

using namespace std;

int w[105], val[105];

long long dp[100005];

int main()

{

    int t,m,res=-1;    

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

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

    {

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

    }

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

    {

        for(int j=t;j>=0;j--) 

        {

            if(j>=w[i])

            {

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

            }

        }

    }    

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

    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.3201846726613313x):
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

typedef pair<int, int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;

typedef vector<ll> vll;



ll dp(int mw, int n, int w[], int v[]){

	long memo[n+1][mw+1];

	int i , j;

//	memset(memo, 0, sizeof memo);

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

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

			if(i ==0 || j ==0)

				memo[i][j] = 0;

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

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

			else

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

//			cout << memo[i][j] << ' ';

		}

//		cout << endl;

	}

//	cout << i << ' ' << j << endl;

	return memo[n][mw];

}



int main() {

	int n, mw;

	cin >> n >> mw;

	int w[n],v[n];

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

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

	}

	cout << dp(mw,n,w,v);

	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.2902247930170034x):
#include<bits/stdc++.h>

#define MAXN 110

#define MAXW 100010

#define ll long long



using namespace std;



ll n, W, ans, w[MAXN], v[MAXN], dp[MAXW];

bool mk[MAXW];



void init(){

    mk[0]=true;

}



int main(){



    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);



    cin>>n>>W;



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

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

    }



    init();



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

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

            if(mk[j]&&dp[j]+v[i]>dp[j+w[i]]){

                mk[j+w[i]]=true;

                dp[j+w[i]]=dp[j]+v[i];

            }

        }

    }



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



    cout<<ans;



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.3114743592958455x):
#include <bits/stdc++.h>



using namespace std;



//Recursive Definition

long long maximumCost(long long * weights, long long * values, long long N, long long W){

if(N == 1){

  if(weights[N-1] <= W){

   return  values[N-1];

  }else{

   return 0;

  }

}else if(N > 1){

  if(weights[N-1] <= W){

   return  max(values[N-1] + maximumCost(weights,values,N-1,W-weights[N-1]),maximumCost(weights,values,N-1,W));

  }else{

   return maximumCost(weights,values,N-1,W);

  }

}

}

//Now Using Memoization

//Bottom up algorithm Reference: https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

long long knapSack(long long W, long long * weights, long long * values, long long N) {

   long long i, w;

   long long WN[N+1][W+1];

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

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

           if (i==0 || w==0){

           WN[i][w] = 0;

           }else if (weights[i-1] <= w){

           WN[i][w] = max(values[i-1] + WN[i-1][w-weights[i-1]],WN[i-1][w]);

           }else{

           WN[i][w] = WN[i-1][w];

           }

       }

   }

   return WN[N][W];

}



int main(){

    long long N;

    cin>>N;

    long long W;

    cin>>W;

    long long * weights = new long long[N];

    long long * values = new long long[N];

    for(long long i = 0; i < N;i++){

     cin>>weights[i];

     cin>>values[i];

    }

  //  cout<<maximumCost(weights,values,N,W)<<endl;

    cout<<knapSack(W,weights,values,N)<<endl;

    delete[] weights;

    delete[] values;

    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.312008380642588x):
#include<iostream>

#include<algorithm>



using namespace std;



const int maxn = 100000+5;

const int inf = 0x3f3f3f3f;

const int maxm=100000+5;



long long a[maxn],t[maxn],f[maxm];



int main(){

	int n,m;

	cin>>n>>m;

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

    	cin>>t[i]>>a[i];

    }

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

    	f[j]=-inf;

    }

    f[0]=0;

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

    	for(int j=m;j>=0;j--){

    		if(j>=t[i]){

    			f[j]=max(f[j],f[j-t[i]]+a[i]);

    		}	

    		}

    }

    long long ret=-1;

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

    	ret=max(ret,f[j]);

    }

cout<<ret <<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: 2.2927736562188743x):
#include <bits/stdc++.h>

using namespace std;

 

int main() {

  int N,W;

 

  cin >> N >> W;

 

  vector<int> w(N), v(N);

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

 

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

    cin >> w[i];

    cin >> v[i];

  }

 

 

 

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

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

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

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

      }

      else {

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

      }

    }

  }

 

  // for(int i=0;i<=N;i++) {

  //   for(int j=0;j<=W;j++) {

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

  //   }

  //   cout << endl;

  // }

 

  cout << dp[N][W] << 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: 2.2848815848543187x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll, ll> pii;

#define fi first 

#define se second

#define endl '\n'



pii arr[105]; //fi = wi; se = vi;

ll dp[105][100005];



int main(){

	

	ios_base::sync_with_stdio(0);

	int n, w; cin >>n >>w;

	

	for(int i = 1; i<=n; i++) cin >>arr[i].fi >>arr[i].se;

	

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

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

			if(j - arr[i].fi >= 0){

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

			}

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

		}

		/*

		for(int j = 1; j <= w; j++) cout <<dp[i][j] <<endl;

		cout <<endl;*/

	}



	cout <<dp[n][w] <<endl;

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>

#include <numeric>

#include <cmath>

#include <set>

#include <tuple>

#include <functional>

#include <map>

#include <unordered_map>

#include <queue>

#include <tuple>



using namespace std;



#define endl '\n'



using ull = unsigned long int;

using ll = long long;



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  const int precision = 13;

  cout.precision(precision);

  cout.setf(ios_base::fixed);



  int n, W; cin >> n >> W;

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



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

    ll w, v; cin >>  w >> v;

    for (int j = W; j - w >= 0; --j) {

      if (j-w == 0 or dp[j-w]) {

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

      }

    }

  }



  cout << *max_element(dp.begin(), dp.end()) << endl;



  return 0;

}


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

#include <stdlib.h>

long long max(long long a,long long b)

{

	if(a>b)	return a;

	return b; 

}

int main()

{

	int i,n,j,W;

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

	long long *dp=(long long*)malloc(sizeof(long long)*W);

	dp[0]=0;

	for(i=1;i<=W;i++) dp[i]=-1;

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

	{

		int w1,v1;

		scanf("%d %d",&w1,&v1);

		for(j=W;j>=0;j--)

		{

			if(dp[j]==-1)	continue;

			if(j+w1<=W) dp[j+w1] = max(dp[j+w1],dp[j]+v1);

		}	

	}

	long long ans=-1;

	for(i=0;i<=W;i++)	

	ans=max(ans,dp[i]);

	printf("%lld",ans);

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

using namespace std;

    long long N,W,k,val[109],we[109],i,j;

        long long Kn[105][100007];

    void knap()

    {

        for(i=0;i<=W;i++)

            Kn[0][i]=0;

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

            Kn[i][0]=0;

//            cout<<"HA";

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

            for(j=1;j<=W;j++)

{

                if(we[i]>j) {

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

//                        cout<<i<<" "<<we[i]<<" "<<j<<" "<<Kn[i][j]<<endl;

                }

                else

                    {

                        Kn[i][j]=max(Kn[i-1][j],val[i]+Kn[i-1][j-we[i]]);

//                        cout<<we[i]<<" "<<j<<" "<<Kn[i][j]<<endl;

                    }

}

        cout<<Kn[N][W]<<endl;

    }

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cin>>N>>W;

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

        cin>>we[i]>>val[i];

        knap();

//        cout<<"?";

        return 0;

}


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

#include <stdlib.h>

long long max(long long a,long long b)

{

	if(a>b)	return a;

	return b; 

}

int main()

{

	int i,n,j,W;

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

	long long *dp=(long long*)malloc(sizeof(long long)*W);

	dp[0]=0;

	for(i=1;i<=W;i++) dp[i]=-1;

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

	{

		int w1,v1;

		scanf("%d %d",&w1,&v1);

		for(j=W;j>=0;j--)

		{

			if(dp[j]==-1)	continue;

			if(j+w1<=W) dp[j+w1] = max(dp[j+w1],dp[j]+v1);

		}	

	}

	long long ans=-1;

	for(i=0;i<=W;i++)	

	ans=max(ans,dp[i]);

	printf("%lld",ans);

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 100000 + 100

#define ll long long int

ll N[MAXN];

ll w[200];

ll v[200];

ll n;

ll max_V;

int main()

{

    cin>>n>>max_V;

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

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

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

        for(int j = max_V;j >= v[i];--j)

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

    cout<<N[max_V]<<endl;



    return 0;

}





//12

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

#include <stdlib.h>

long long max(long long a,long long b)

{

	if(a>b)	return a;

	return b; 

}

int main()

{

	int i,n,j,W;

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

	long long *dp=(long long*)malloc(sizeof(long long)*W);

	dp[0]=0;

	for(i=1;i<=W;i++) dp[i]=-1;

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

	{

		int w1,v1;

		scanf("%d %d",&w1,&v1);

		for(j=W;j>=0;j--)

		{

			if(dp[j]==-1)	continue;

			if(j+w1<=W) dp[j+w1] = max(dp[j+w1],dp[j]+v1);

		}	

	}

	long long ans=-1;

	for(i=0;i<=W;i++)	

	ans=max(ans,dp[i]);

	printf("%lld",ans);

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

using namespace std;



int main(){



    int s, n, ans = 0;



    cin >> s >> n;

    long long w[s + 5], v[s + 5];

    for(int i = 1; i <= s; i++) cin >> w[i] >> v[i];

    long long dp[s + 5][n + 5];

    memset(dp, 0, sizeof(dp));

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

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

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

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

        }

    }

    cout << dp[s][n] << endl;



    return 0;

}


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

#include <stdlib.h>

long long max(long long a,long long b)

{

	if(a>b)	return a;

	return b; 

}

int main()

{

	int i,n,j,W;

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

	long long *dp=(long long*)malloc(sizeof(long long)*W);

	dp[0]=0;

	for(i=1;i<=W;i++) dp[i]=-1;

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

	{

		int w1,v1;

		scanf("%d %d",&w1,&v1);

		for(j=W;j>=0;j--)

		{

			if(dp[j]==-1)	continue;

			if(j+w1<=W) dp[j+w1] = max(dp[j+w1],dp[j]+v1);

		}	

	}

	long long ans=-1;

	for(i=0;i<=W;i++)	

	ans=max(ans,dp[i]);

	printf("%lld",ans);

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



#define filein freopen ("in.txt", "r", stdin)

#define fileout freopen ("out.txt", "w", stdout)

#define dbg(x) cerr << #x << ": " << x << endl



using namespace std;

typedef long long ll;



const int maxn = 102;



ll w[maxn];

ll v[maxn];

ll dp[maxn][100005];



int main(){

	ll n, W;

	scanf ("%lld %lld", &n, &W);

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

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

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

		for (ll j = 1; j <= W; j++){

			if (j < w[i])

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

			else

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

		}

	}

	cout << dp[n][W] << '\n';

	return 0;

}

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

#include <stdlib.h>

long long max(long long a,long long b)

{

	if(a>b)	return a;

	return b; 

}

int main()

{

	int i,n,j,W;

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

	long long *dp=(long long*)malloc(sizeof(long long)*W);

	dp[0]=0;

	for(i=1;i<=W;i++) dp[i]=-1;

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

	{

		int w1,v1;

		scanf("%d %d",&w1,&v1);

		for(j=W;j>=0;j--)

		{

			if(dp[j]==-1)	continue;

			if(j+w1<=W) dp[j+w1] = max(dp[j+w1],dp[j]+v1);

		}	

	}

	long long ans=-1;

	for(i=0;i<=W;i++)	

	ans=max(ans,dp[i]);

	printf("%lld",ans);

}
// Slower C++ solution:
#include <cstring>

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <sstream>

#include <queue>

#include <deque>

#include <bitset>

#include <iterator>

#include <list>

#include <stack>

#include <map>

#include <set>

#include <functional>

#include <numeric>

#include <utility>



#include <cmath>

#include <iomanip>



using namespace std;



int main()

{

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n;

  cin >> n;

  int w;

  cin >> w;

  int weights[n];

  long long int values[n];

  long long int cur;

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

    cin >> cur;

    weights[i] = cur;

    cin >> cur;

    values[i] = cur;

  }

  long long int dp[n+1][w+1];

  // dp[n][w] represents the maximum value that can be achieved with at most w weight and only using items with number up to n.

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

    for (int j = 0; j < w+1; j++) {

      dp[i][j] = 0;

    }

  }

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

    for (int allowed = 0; allowed < w; allowed++) {

      dp[minInd+1][allowed] = max(dp[minInd+1][allowed], dp[minInd][allowed]);

      if (allowed+weights[minInd] <= w) {

	dp[minInd+1][allowed+weights[minInd]] = max(dp[minInd+1][allowed+weights[minInd]], dp[minInd][allowed]+values[minInd]);

      }

    }

  }

  long long int best = dp[n][0];

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

    best = max(best, dp[n][i]);

  }

  cout << best << "\n";

  return 0;

}

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

#include <stdlib.h>

long long max(long long a,long long b)

{

	if(a>b)	return a;

	return b; 

}

int main()

{

	int i,n,j,W;

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

	long long *dp=(long long*)malloc(sizeof(long long)*W);

	dp[0]=0;

	for(i=1;i<=W;i++) dp[i]=-1;

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

	{

		int w1,v1;

		scanf("%d %d",&w1,&v1);

		for(j=W;j>=0;j--)

		{

			if(dp[j]==-1)	continue;

			if(j+w1<=W) dp[j+w1] = max(dp[j+w1],dp[j]+v1);

		}	

	}

	long long ans=-1;

	for(i=0;i<=W;i++)	

	ans=max(ans,dp[i]);

	printf("%lld",ans);

}
// 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: 12.102749488309533x):
#include <stdio.h>

#include <stdlib.h>

long long max(long long a,long long b)

{

	if(a>b)	return a;

	return b; 

}

int main()

{

	int i,n,j,W;

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

	long long *dp=(long long*)malloc(sizeof(long long)*W);

	dp[0]=0;

	for(i=1;i<=W;i++) dp[i]=-1;

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

	{

		int w1,v1;

		scanf("%d %d",&w1,&v1);

		for(j=W;j>=0;j--)

		{

			if(dp[j]==-1)	continue;

			if(j+w1<=W) dp[j+w1] = max(dp[j+w1],dp[j]+v1);

		}	

	}

	long long ans=-1;

	for(i=0;i<=W;i++)	

	ans=max(ans,dp[i]);

	printf("%lld",ans);

}