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

//#pragma GCC optimize("Ofast")

//#pragma GCC target("avx,avx2,fma")



using namespace std;



typedef long long ll;



//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>pb_ds;



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

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

#define pi pair<int,int>

#define F first

#define S second

#define pb push_back

#define pp pop_back

#define mod 1000000007

#define pai acos(-1)

#define N 100005



ll Weight[N],Profit[N],dp[2][N];



int main ()

{

   ios_base::sync_with_stdio(false);

   cin.tie(NULL);

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

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

      cin>>Weight[i]>>Profit[i];

   }

   fill(dp[0],dp[0]+2*N,-INT_MAX*105);

   dp[(n+1)%2][0]=0;

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

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

         ll op1=dp[(i+1)%2][s];

         ll op2=(s-Weight[i]>=0)?Profit[i]+dp[(i+1)%2][s-Weight[i]]:0ll;

         dp[i%2][s]=max(op1,op2);

      }

   }

   ll ans=0;

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

   cout<<ans<<"\n";

   return 0;

}




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

using namespace std;

typedef long long int ll;



ll dp[100005][105];



int main(){

    ios::sync_with_stdio(false);

    cin.tie(NULL); cout.tie(NULL);





    int n, W;

    cin>>n>>W;



    vector<int> weights(n), values(n);



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

        cin>>weights[i];

        cin>>values[i];

    }





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

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

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



            if(w >= weights[i])

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

        }

    }



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





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

using namespace std;



#define gap " "

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

#define rall(v) v.rbegin(),v.rend()

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

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

#define dbg(x) cout<<(#x)<<" is "<<x<<endl

#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}





typedef long long ll;



ll dp[102][100005];

ll wt[102],val[102];



ll knapsack(int n,int w)

{



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

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

         if(i==0 || j==0) dp[i][j]=0;

         else if(wt[i]<=j){

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

         }

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

      }

     

   }

   return dp[n][w];

}

int main()

{

   ll n,w,i;

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

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

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

   }

   ll ans=knapsack(n,w);

   printf("%lld\n",ans);

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

using namespace std;



#define gap " "

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

#define rall(v) v.rbegin(),v.rend()

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

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

#define dbg(x) cout<<(#x)<<" is "<<x<<endl

#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}





typedef long long ll;



ll dp[102][100005];

ll wt[102],val[102];



ll knapsack(int n,int w)

{



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

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

         if(i==0 || j==0) dp[i][j]=0;

         else if(wt[i]<=j){

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

         }

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

      }

     

   }

   return dp[n][w];

}

int main()

{

   ll n,w,i;

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

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

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

   }

   ll ans=knapsack(n,w);

   printf("%lld\n",ans);

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

using namespace std;



#define gap " "

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

#define rall(v) v.rbegin(),v.rend()

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

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

#define dbg(x) cout<<(#x)<<" is "<<x<<endl

#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}





typedef long long ll;



ll dp[102][100005];

ll wt[102],val[102];



ll knapsack(int n,int w)

{



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

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

         if(i==0 || j==0) dp[i][j]=0;

         else if(wt[i]<=j){

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

         }

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

      }

     

   }

   return dp[n][w];

}

int main()

{

   ll n,w,i;

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

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

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

   }

   ll ans=knapsack(n,w);

   printf("%lld\n",ans);

   return 0;

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

using namespace std;



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

#define fp(i,a,b) for(int i=a ; i<b ; i++)

#define fn(i,a,b) for(int i=a ; i>=b ; i--)

#define pb push_back

#define mk make_pair

#define ff first

#define ss second

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



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;

typedef vector<ll> vll;



const int M=1e5+5;

const ll INF=1e15;

const int MOD=1e9+5;



int n,W;

ll dp[M][105],valor[105],peso[105];



ll ks(int w,int x){

  if (w < 0) return -INF;

  if (x > n) return 0;

  if (dp[w][x] != -1) return dp[w][x];

  dp[w][x] = max(ks(w,x+1) , valor[x] + ks(w-peso[x],x+1));

  return dp[w][x];

}



void ini(){

  fp(i,0,M)

    fp(j,1,n+1) dp[i][j] = -1;

}



int main(){



	fastio;

  cin >> n >> W;

  ini();

  fp(i,1,n+1) cin >> peso[i] >> valor[i];

  cout << ks(W,1) << "\n";



	return 0;

}


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

using namespace std;



#define gap " "

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

#define rall(v) v.rbegin(),v.rend()

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

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

#define dbg(x) cout<<(#x)<<" is "<<x<<endl

#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}





typedef long long ll;



ll dp[102][100005];

ll wt[102],val[102];



ll knapsack(int n,int w)

{



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

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

         if(i==0 || j==0) dp[i][j]=0;

         else if(wt[i]<=j){

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

         }

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

      }

     

   }

   return dp[n][w];

}

int main()

{

   ll n,w,i;

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

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

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

   }

   ll ans=knapsack(n,w);

   printf("%lld\n",ans);

   return 0;

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

//#pragma GCC optimize("Ofast")

//#pragma GCC target("avx,avx2,fma")



using namespace std;



typedef long long ll;



//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>pb_ds;



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

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

#define pi pair<int,int>

#define F first

#define S second

#define pb push_back

#define pp pop_back

#define mod 1000000007

#define pai acos(-1)

#define N 100005



ll Weight[N],Profit[N],dp[2][N];



int main ()

{

   ios_base::sync_with_stdio(false);

   cin.tie(NULL);

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

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

      cin>>Weight[i]>>Profit[i];

   }

   fill(dp[0],dp[0]+2*N,-INT_MAX*105);

   dp[(n+1)%2][0]=0;

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

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

         ll op1=dp[(i+1)%2][s];

         ll op2=(s-Weight[i]>=0)?Profit[i]+dp[(i+1)%2][s-Weight[i]]:0ll;

         dp[i%2][s]=max(op1,op2);

      }

   }

   ll ans=0;

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

   cout<<ans<<"\n";

   return 0;

}




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

using namespace std;



#define gap " "

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

#define rall(v) v.rbegin(),v.rend()

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

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

#define dbg(x) cout<<(#x)<<" is "<<x<<endl

#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}





typedef long long ll;



ll dp[102][100005];

ll wt[102],val[102];



ll knapsack(int n,int w)

{



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

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

         if(i==0 || j==0) dp[i][j]=0;

         else if(wt[i]<=j){

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

         }

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

      }

     

   }

   return dp[n][w];

}

int main()

{

   ll n,w,i;

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

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

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

   }

   ll ans=knapsack(n,w);

   printf("%lld\n",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.280984736902449x):
#include <bits/stdc++.h>

using namespace std;



const int MAX_N = 1e5 + 5;

const int MAX_L = 20; // ~ Log N

const long long MOD = 1e9 + 7;

const long long INF = 1e9 + 7;



typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<vi> vvi;



int w[101], v[101];



ll solve(int n, int m, vector<vector<ll>> dp){

	

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

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

			if(w[i] <= j)

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

			else

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

		}

	}

	return dp[n][m];

}



int main(){

	ios_base::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);

    

    //freopen("input.txt", "r", stdin);

    //freopen("output.txt", "w", stdout);

	

/*	int t;

	cin >> t;

	while(t--){

		//cout << "Case #" << t  << ": ";

        

	} */

	int n, m;

	cin >> n >> m;

	

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

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

	

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

	ll ans = solve(n, m, dp);

	cout << ans;

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

using namespace std;



const int MAX_N = 1e5 + 5;

const int MAX_L = 20; // ~ Log N

const long long MOD = 1e9 + 7;

const long long INF = 1e9 + 7;



typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<vi> vvi;



int w[101], v[101];



ll solve(int n, int m, vector<vector<ll>> dp){

	

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

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

			if(w[i] <= j)

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

			else

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

		}

	}

	return dp[n][m];

}



int main(){

	ios_base::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);

    

    //freopen("input.txt", "r", stdin);

    //freopen("output.txt", "w", stdout);

	

/*	int t;

	cin >> t;

	while(t--){

		//cout << "Case #" << t  << ": ";

        

	} */

	int n, m;

	cin >> n >> m;

	

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

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

	

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

	ll ans = solve(n, m, dp);

	cout << ans;

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

using namespace std;



const int MAX_N = 1e5 + 5;

const int MAX_L = 20; // ~ Log N

const long long MOD = 1e9 + 7;

const long long INF = 1e9 + 7;



typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<vi> vvi;



int w[101], v[101];



ll solve(int n, int m, vector<vector<ll>> dp){

	

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

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

			if(w[i] <= j)

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

			else

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

		}

	}

	return dp[n][m];

}



int main(){

	ios_base::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);

    

    //freopen("input.txt", "r", stdin);

    //freopen("output.txt", "w", stdout);

	

/*	int t;

	cin >> t;

	while(t--){

		//cout << "Case #" << t  << ": ";

        

	} */

	int n, m;

	cin >> n >> m;

	

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

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

	

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

	ll ans = solve(n, m, dp);

	cout << ans;

	return 0;

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

using namespace std;



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

#define fp(i,a,b) for(int i=a ; i<b ; i++)

#define fn(i,a,b) for(int i=a ; i>=b ; i--)

#define pb push_back

#define mk make_pair

#define ff first

#define ss second

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



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;

typedef vector<ll> vll;



const int M=1e5+5;

const ll INF=1e15;

const int MOD=1e9+5;



int n,W;

ll dp[M][105],valor[105],peso[105];



ll ks(int w,int x){

  if (w < 0) return -INF;

  if (x > n) return 0;

  if (dp[w][x] != -1) return dp[w][x];

  dp[w][x] = max(ks(w,x+1) , valor[x] + ks(w-peso[x],x+1));

  return dp[w][x];

}



void ini(){

  fp(i,0,M)

    fp(j,1,n+1) dp[i][j] = -1;

}



int main(){



	fastio;

  cin >> n >> W;

  ini();

  fp(i,1,n+1) cin >> peso[i] >> valor[i];

  cout << ks(W,1) << "\n";



	return 0;

}


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

using namespace std;



const int MAX_N = 1e5 + 5;

const int MAX_L = 20; // ~ Log N

const long long MOD = 1e9 + 7;

const long long INF = 1e9 + 7;



typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<vi> vvi;



int w[101], v[101];



ll solve(int n, int m, vector<vector<ll>> dp){

	

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

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

			if(w[i] <= j)

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

			else

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

		}

	}

	return dp[n][m];

}



int main(){

	ios_base::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);

    

    //freopen("input.txt", "r", stdin);

    //freopen("output.txt", "w", stdout);

	

/*	int t;

	cin >> t;

	while(t--){

		//cout << "Case #" << t  << ": ";

        

	} */

	int n, m;

	cin >> n >> m;

	

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

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

	

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

	ll ans = solve(n, m, dp);

	cout << ans;

	return 0;

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

//#pragma GCC optimize("Ofast")

//#pragma GCC target("avx,avx2,fma")



using namespace std;



typedef long long ll;



//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>pb_ds;



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

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

#define pi pair<int,int>

#define F first

#define S second

#define pb push_back

#define pp pop_back

#define mod 1000000007

#define pai acos(-1)

#define N 100005



ll Weight[N],Profit[N],dp[2][N];



int main ()

{

   ios_base::sync_with_stdio(false);

   cin.tie(NULL);

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

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

      cin>>Weight[i]>>Profit[i];

   }

   fill(dp[0],dp[0]+2*N,-INT_MAX*105);

   dp[(n+1)%2][0]=0;

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

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

         ll op1=dp[(i+1)%2][s];

         ll op2=(s-Weight[i]>=0)?Profit[i]+dp[(i+1)%2][s-Weight[i]]:0ll;

         dp[i%2][s]=max(op1,op2);

      }

   }

   ll ans=0;

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

   cout<<ans<<"\n";

   return 0;

}




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

using namespace std;



const int MAX_N = 1e5 + 5;

const int MAX_L = 20; // ~ Log N

const long long MOD = 1e9 + 7;

const long long INF = 1e9 + 7;



typedef long long ll;

typedef vector<int> vi;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<vi> vvi;



int w[101], v[101];



ll solve(int n, int m, vector<vector<ll>> dp){

	

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

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

			if(w[i] <= j)

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

			else

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

		}

	}

	return dp[n][m];

}



int main(){

	ios_base::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);

    

    //freopen("input.txt", "r", stdin);

    //freopen("output.txt", "w", stdout);

	

/*	int t;

	cin >> t;

	while(t--){

		//cout << "Case #" << t  << ": ";

        

	} */

	int n, m;

	cin >> n >> m;

	

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

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

	

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

	ll ans = solve(n, m, dp);

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

#include <vector>

#include <cmath>

#include <set>

#include <queue>

#include <map>

#include <cstdio>

#include <cstring>

#include <string>

#include <stack>

#include <algorithm>

#include <limits.h>

#include <bits/stdc++.h>

#define fw(x) freopen("x.txt","w",stdout)

#define For(i,a,b,c) for(int i = a;i < b;i+=c)

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

#define REP1(i,n) for(int i = 1; i<=n;i++)

#define mem(a,s) memset(a,s,sizeof a)

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

#define pf printf

#define sc scanf

#define ll long long

#define pii pair<int,int>

#define pll pair<ll,ll>

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

#define vii vector<int>

#define vll vector<ll>

#define vss vector<string>

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

#define pb push_back





using namespace std;





// moves



//int dx[]= {0,0,1,-1};/*4 side move*/

//int dy[]= {-1,1,0,0};/*4 side move*/

//int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/

//int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/

//int dx[]={1,1,2,2,-1,-1,-2,-2};/*knight move*/

//int dy[]={2,-2,1,-1,2,-2,1,-1};/*knight move*/





//big_mod



//ll bigmod(ll a,ll b,ll m)

//{if(b == 0) return 1%m;ll x = bigmod(a,b/2,m);x = (x * x) % m;if(b % 2 == 1) x = (x * a)% m;return x;}

//ll BigMod(ll B,ll P,ll M){ ll R=1%M; while(P>0) {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;} /// (B^P)%M



//ll getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1ll;}

//ll setBit1(ll num, int idx) {return num or (1ll<<idx);}

//ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}

//ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}



const int mod = 1000000007;



    int cost[101];

    int wt[101];

    ll dp[101][100001];

int main()

{

    fast;

    int n, w;

    cin>>n>>w;

    REP1(i, n) cin>>wt[i]>>cost[i];

    REP1(i, n){

      REP1(j, w){

        if(j>=wt[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i]] + cost[i]);

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

      }

    }

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

    return 0;

}