stablegradients/pie-gem5-pairs huggingface dataset:
// 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.789619441498841x):
#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;

}
// 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.7797625812830278x):
#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;

}
// 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.002607732770425x):
#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;

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

using namespace std;

#define fastIO ios::sync_with_stdio(0), cin.tie(0)

#define endl '\n'

#define ft first

#define sd second

#define pb push_back

#define pob pop_back()

#define pf push_front

#define pof pop_front()

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

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

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<char,char> pcc;

typedef pair<double,double> pdd;

typedef pair<long long,long long> pll;

// scanf("%d %d %d %d",&w,&b,&d,&s); %lld

// printf("%d\n" ,points);

// const double PI=acos(-1);



const int MAX = 1e5+4;

ll dp[102][MAX];



int main(){

    fastIO;

    int n, w;

    cin >> n >> w;

    int weights[n], values[n];

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

        cin >> weights[i] >> values[i];

    }



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

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

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

            if(j-weights[i-1] > -1){

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

            }

        }

    }

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

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

using namespace std;

#define fastIO ios::sync_with_stdio(0), cin.tie(0)

#define endl '\n'

#define ft first

#define sd second

#define pb push_back

#define pob pop_back()

#define pf push_front

#define pof pop_front()

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

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

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<char,char> pcc;

typedef pair<double,double> pdd;

typedef pair<long long,long long> pll;

// scanf("%d %d %d %d",&w,&b,&d,&s); %lld

// printf("%d\n" ,points);

// const double PI=acos(-1);



const int MAX = 1e5+4;

ll dp[102][MAX];



int main(){

    fastIO;

    int n, w;

    cin >> n >> w;

    int weights[n], values[n];

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

        cin >> weights[i] >> values[i];

    }



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

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

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

            if(j-weights[i-1] > -1){

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

            }

        }

    }

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

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

using namespace std;

#define fastIO ios::sync_with_stdio(0), cin.tie(0)

#define endl '\n'

#define ft first

#define sd second

#define pb push_back

#define pob pop_back()

#define pf push_front

#define pof pop_front()

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

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

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<char,char> pcc;

typedef pair<double,double> pdd;

typedef pair<long long,long long> pll;

// scanf("%d %d %d %d",&w,&b,&d,&s); %lld

// printf("%d\n" ,points);

// const double PI=acos(-1);



const int MAX = 1e5+4;

ll dp[102][MAX];



int main(){

    fastIO;

    int n, w;

    cin >> n >> w;

    int weights[n], values[n];

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

        cin >> weights[i] >> values[i];

    }



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

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

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

            if(j-weights[i-1] > -1){

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

            }

        }

    }

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

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

using namespace std;

#define fastIO ios::sync_with_stdio(0), cin.tie(0)

#define endl '\n'

#define ft first

#define sd second

#define pb push_back

#define pob pop_back()

#define pf push_front

#define pof pop_front()

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

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

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<char,char> pcc;

typedef pair<double,double> pdd;

typedef pair<long long,long long> pll;

// scanf("%d %d %d %d",&w,&b,&d,&s); %lld

// printf("%d\n" ,points);

// const double PI=acos(-1);



const int MAX = 1e5+4;

ll dp[102][MAX];



int main(){

    fastIO;

    int n, w;

    cin >> n >> w;

    int weights[n], values[n];

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

        cin >> weights[i] >> values[i];

    }



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

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

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

            if(j-weights[i-1] > -1){

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

            }

        }

    }

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

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

using namespace std;

#define fastIO ios::sync_with_stdio(0), cin.tie(0)

#define endl '\n'

#define ft first

#define sd second

#define pb push_back

#define pob pop_back()

#define pf push_front

#define pof pop_front()

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

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

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<char,char> pcc;

typedef pair<double,double> pdd;

typedef pair<long long,long long> pll;

// scanf("%d %d %d %d",&w,&b,&d,&s); %lld

// printf("%d\n" ,points);

// const double PI=acos(-1);



const int MAX = 1e5+4;

ll dp[102][MAX];



int main(){

    fastIO;

    int n, w;

    cin >> n >> w;

    int weights[n], values[n];

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

        cin >> weights[i] >> values[i];

    }



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

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

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

            if(j-weights[i-1] > -1){

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

            }

        }

    }

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

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define gg(x) getInt(&x)

using namespace std;

typedef long long ll;

inline void getInt(int* p);

const int maxn=1000010;

const int inf=0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

int n,m;

int w[maxn];

ll v[maxn];

ll dp[maxn];

int main()

{

    gbtb;

    cin>>n>>m;

    repd(i,1,n)

    {

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

    }

    repd(i,1,n)

    {

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

        {

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

        }

    }

    cout<<dp[m];

    return 0;

}



inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    }

    else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '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.7873360812801564x):
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define gg(x) getInt(&x)

using namespace std;

typedef long long ll;

inline void getInt(int* p);

const int maxn=1000010;

const int inf=0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

int n,m;

int w[maxn];

ll v[maxn];

ll dp[maxn];

int main()

{

    gbtb;

    cin>>n>>m;

    repd(i,1,n)

    {

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

    }

    repd(i,1,n)

    {

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

        {

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

        }

    }

    cout<<dp[m];

    return 0;

}



inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    }

    else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}