stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}	

// Faster C++ solution for the same problem (measured speedup: 5.295546098132272x):


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



long long  knapSack(long long W, long long wt[], long long val[], long long n) 

{  

      

long long i, w; 

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

  

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

   { 

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

       { 

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

               K[i][w] = 0; 

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

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

           else

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

       } 

   } 

  

   return K[n][W]; 

} 





int main() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, 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.2845122494910446x):
#include <bits/stdc++.h>



#define ll long long

#define lp(i,n) for(int i=0; i<n; i++)

#define pb push_back

const long double pi=3.141592654;

#define OSOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;



const ll inf = 1e9 +5, mod = 1e9+7,N = 1e5+5;



    int val[N],weights[N];

    ll dp[102][N];

int main()

{

    OSOS

	ll n,w;

    cin>>n>>w;



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

    	cin>>weights[i]>>val[i];



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

    for(int rem = 1; rem <= w; rem++)

    	{

    		ll op1,op2;

    		op1 = dp[item-1][rem];

    		op2 = 0;

    		if(rem >= weights[item])

    		{

    			op2 = val[item] + dp[item-1][rem - weights[item]];

    		}

    		dp[item][rem] = max(op1,op2);

    	}



    cout<<dp[n][w];



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

#include <string>

#include<iomanip>

#include <algorithm>

#include <map>

#include <vector>

#include<queue>

#include<math.h>

#include<cmath>

#include<sstream>

#include<set>

#include <map>

#include<string.h>

#include<sstream>

#include<stack>

#include<unordered_map>

#include <iostream>

#include <stdio.h>

#include <ctype.h>

#include <cstdio>

#include <cstdlib>

#define ll long long

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e5 + 5, inf = 1e9 + 7;

const double ep = 0.0000000001;

const double pi = 3.14159265359;

	

	long long   dp[100005][105];

int main()

{

	int  n, m;

	cin >> n >> m;

	pair <int ,int >arr[105];

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

		cin >> arr[i].first>>arr[i].second;//weight ///price 

	}

	

	dp[m][0] = 0;

	if (m >= arr[0].first) {

		dp[m-arr[0].first][0] = arr[0].second;//m-arr[0].first -->ro7 3la w ely hy5leny 4-1[3][0][cap][item]

	}

	ll  ans=0;//

	for (int item = 1; item <= n; item++) {//colom

		for (int w = 1; w <= m; w++) {//row

				    ll op1 = dp[w][item-1 ];

					ll op2 = 0;

	               if (w >= arr[item].first) 

					 op2 = arr[item].second + dp[w - arr[item].first][item - 1]; 

					dp[w ][item] = max(op1, op2);

						}

			 }	

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

using namespace std;

#define f first

#define s second

#define ll long long

const int N = 1e5+50 ;

ll dp[102][N], v[N], w[N], n, s;

int main()

{

    cin >> n >> s ;

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

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

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

    {

        for ( int c = 1 ; c <= s ; c++)

        {

            ll opt1 = dp[i-1][c] ;

            ll opt2 = 0 ;

            if ( c >= w[i]){

                opt2 += dp[i-1][c-w[i]]+v[i];

            }

            dp[i][c] = max(opt1,opt2);

        }

    }

    cout << dp[n][s];

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

    using namespace std ;

    #define ll long long



    inline int D(){

        int t ;

        scanf( "%d" , &t ) ;

        return t ;

    }

    inline ll LLD(){

        ll t ;

        scanf( "%lld" , &t ) ;

        return t ;

    }

   // const int INF = 0x3f3f3f3f;

//###################################################################

const int maxw=100000,N=105;

int n,W,w[N],v[N];

ll dp[N][maxw];

int main(){

    n=D(),W=D();

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

        w[i]=D();

        v[i]=D();

    }

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

        if(i>=w[0])dp[0][i]=v[0];



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

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

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

            else{

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

            }

        }

    }

    printf("%lld",dp[n-1][W]);

}
// 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.3199627736952757x):
#define f(i,s,v) for(int i=(int)s;i<(int)v;++i)

#define rf(i,s,v) for(int i=(int)s-1;i>(int)v;--i)

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll oo=1e15;

int n,cap,w[100005],v[100005];

int main()

{

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

    f(i,0,n)

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

    ll knapsack[n+1][cap+1];

    f(i,0,n+1){

       f(j,0,cap+1){

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

               knapsack[i][j] = 0;

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

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

           else

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

       }



   }

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

using namespace std;



unsigned long long knapsack(vector<unsigned long long>&weight,vector<unsigned long long>&value,int n,int W)

{   vector<vector<unsigned long long > >dp(n+1,vector<unsigned long long>(W+1,0));

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

    {

      for(unsigned long long w = 1;w<=W;w++)

      {   if(w>=weight[i-1])

        dp[i][w] = max(value[i-1]+dp[i-1][w-weight[i-1]],dp[i-1][w]);

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

      }

         

    }

    return dp[weight.size()][W];

}

int main()

{

     int n,W;

  cin>>n>>W;

  vector<unsigned long long>weight(n),value(n);

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

  {

    cin>>weight[i]>>value[i];

  }

  cout<<knapsack(weight,value,n,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.345757164136396x):
#include <bits/stdc++.h>

using namespace std;

int n, w, wi[105], vi[105];

long long dp[105][100005];



int main(){

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

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

		scanf("%d%d", &wi[i], &vi[i]);

	}

	

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

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

			if (j < wi[i]){

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

			} else {

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

			}

		}

	}

	

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

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

using namespace std;

long long int solve(vector<int>&weight,vector<long long int>&value,int w){

    vector< long long int>dp(w+1,0);

    

    for(int i=0;i<weight.size();i++){

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

            if(j>=weight[i])

            dp[j]=max(dp[j],value[i]+dp[j-weight[i]]);

            

            

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

        

        }

        // cout<<endl;

    }

    return dp[w];

}











int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    int n;

    int w;

    cin>>n>>w;

    vector<int>weight;

    vector<long long int>value;

    while(n-->0){

        int a,b;

        cin>>a>>b;

        

        weight.push_back(a);

        value.push_back(b);

    }

    cout<<solve(weight,value,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.2865208100726875x):
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define f first

#define s second

#define pb push_back

#define pi acos(-1)

ll mod=998244353;

 

ll po(ll a,ll p)

{

    if(p==0)

        return 1ll;

    else if(p==1)

        return a%mod;

    else if(p%2)

    {

        ll temp=po(a,p/2);

        return ((((temp%mod)*(temp%mod))%mod*(a%mod)))%mod;

    }

    else

    {

        ll temp=po(a,p/2);

        return ((temp%mod)*(temp%mod))%mod;

    }

}



int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    

    ll t, n, m, tc = 0;

    cin >> n >> m;

    ll val[n+5] = {0}, weight[n+5] = {0};

    ll arr[n+5][m+5] = {0};

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

    {

        cin >> weight[i] >> val[i];

    }

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

    {

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

        {

            if(!i || !j)

            {

                arr[i][j] = 0;

            }

            else if (weight[i] <= j)

            {

                arr[i][j] = max(val[i]+arr[i-1][j-weight[i]], arr[i-1][j]);

            }

            else

            {

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

            }

        }

    }

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

using namespace std;

#define ll long long

#define pb push_back

#define mp make_pair

#define ull  unsigned long long

#define vll  vector <long long>

#define pll pair <long long,long long>

#define f first

#define s second

#define up upper_bound

#define lp lower_bound

#define pq priority_queue

#define inf 1e10

#define minf -1e10

#define pi 3.14159265

#define mod 300000000000000000

#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);

int main()

{

  ll n,W;

  cin>>n>>W;

  vector <pll> vec;

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

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

  {

      ll num,num1;

      cin>>num>>num1;

      vec.pb(mp(num,num1));

  }

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

  {

      for(ll j=0;j<=W;j++)

      {

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

          {

              ara[i][j]=0;

          }

          else if(vec[i-1].f<=j)

          {

              ara[i][j]=max(vec[i-1].s+ara[i-1][j-vec[i-1].f],ara[i-1][j]);

          }

          else

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

      }

  }

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

using namespace std;

#define vb __int128

#define ll long long

#define ld long double

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

#define stoink stack<ll>

#define vec vector <ll>

#define vg vector<vector<ll> >

#define vgw vector<vector<pair<ll,ll> >

#define pa pair<ll,ll>

#define mp make_pair

#define pb push_back

#define ff first

#define ss second

#define pre 0.00000000000000000001

#define inf 1000000000000

#define mod 998244353

ll n;

vg dp;

vec weight,value;

ll func(ll ind,ll w) {

	if(ind == n)

		return 0;

	if(dp[ind][w] != -1)

		return dp[ind][w];

	ll res;

	if(weight[ind] > w)

		res = func(ind + 1,w);

	else

		res = max(func(ind + 1,w),func(ind + 1,w - weight[ind]) + value[ind]);

	return dp[ind][w] = res;

}

int main()

{	ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);

	ll w;

	cin >> n >> w;

	dp.resize(n,vector<ll>(w + 1,-1));

	weight.resize(n);

	value.resize(n);

	ll i;

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

		cin >> weight[i] >> value[i];

	cout << func(0,w);

	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.259515114804534x):
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

#include<unordered_map>

using namespace std;

//<DEFINE>

void Fast() {

	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

}

void File() {

#ifndef ONLINE_JUDGE

	freopen("Input.txt", "r", stdin);

	freopen("Output.txt", "w", stdout);

#endif

}

#ifdef _MSC_VER

#include <intrin.h>

#define __builtin_popcount __popcnt

#ifdef _WIN64

#define __builtin_popcountll __popcnt64

#else

inline int __builtin_popcountll(__int64 a) {

	return __builtin_popcount((unsigned int)a) + __builtin_popcount(a >> 32);

}

#endif

#endif

using ll = long long;

using ull = unsigned long long;

#define mod 1000000007

ll gcd(ll a, ll b) {

	return!b ? a : gcd(b, a % b);

}

#define fix(n) cout << fixed << setprecision(n);

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

#define skip continue

#define stop(n) return cout<<n,0

#define pi  acos(-1)

#define endl "\n"

#define ceil(x,y) (x+y-1)/y//be careful from the multiplication while using this define 

#define TC int t;cin>>t;while(t--)

//</DEFINE>

int n, m;

vector<vector<int>>v;

//<FUNCTIONS>

//</FUNCTIONS>	

int main() {

	Fast();

	int n, cpcty;

	cin >> n >> cpcty;

	vector<vector<ll>>dp(n, vector<ll>(cpcty + 1));

	vector<pair<ll, ll>>v(n);

	for (int i = 0; i < n; i++)cin >> v[i].first >> v[i].second;

	for (int i = v[n - 1].first; i <= cpcty; i++)dp[n - 1][i] = v[n - 1].second;

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

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

			if (j >= v[i].first)dp[i][j] = max(dp[i + 1][j - v[i].first] + v[i].second, dp[i + 1][j]);

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

		}

	}

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

}