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

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.991121382161598x):
#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>

//#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.587295250548336x):
#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>

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.3276637950021533x):
/*Rabbi Zidni Ilma*/



#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define scl(n) scanf("%lld",&n)

#define scll(n,m) scanf("%lld%lld",&n,&m)

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define mod 1000000007

#define read freopen("input.txt","r",stdin)

#define write freopen("output.txt","w",stdout)



ll dp[105][100005],w[100005],p[100005];



int main()

{

	ll n,c,i,j;

    scll(n,c);

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

    scll(w[i],p[i]);

    

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

    {

    	for(j=0;j<=c;j++)

    	{

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

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

    		else

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

		}

	}

	ll ans=0;

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

	{

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

	}

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

}
// 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.8201748811422687x):
/*Rabbi Zidni Ilma*/



#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define scl(n) scanf("%lld",&n)

#define scll(n,m) scanf("%lld%lld",&n,&m)

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define mod 1000000007

#define read freopen("input.txt","r",stdin)

#define write freopen("output.txt","w",stdout)



ll dp[105][100005],w[100005],p[100005];



int main()

{

	ll n,c,i,j;

    scll(n,c);

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

    scll(w[i],p[i]);

    

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

    {

    	for(j=0;j<=c;j++)

    	{

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

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

    		else

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

		}

	}

	ll ans=0;

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

	{

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

	}

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

}
// 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.8101497277740601x):
/*Rabbi Zidni Ilma*/



#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define scl(n) scanf("%lld",&n)

#define scll(n,m) scanf("%lld%lld",&n,&m)

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define mod 1000000007

#define read freopen("input.txt","r",stdin)

#define write freopen("output.txt","w",stdout)



ll dp[105][100005],w[100005],p[100005];



int main()

{

	ll n,c,i,j;

    scll(n,c);

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

    scll(w[i],p[i]);

    

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

    {

    	for(j=0;j<=c;j++)

    	{

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

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

    		else

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

		}

	}

	ll ans=0;

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

	{

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

	}

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

}
// 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.156315627775042x):
/*Rabbi Zidni Ilma*/



#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define scl(n) scanf("%lld",&n)

#define scll(n,m) scanf("%lld%lld",&n,&m)

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define mod 1000000007

#define read freopen("input.txt","r",stdin)

#define write freopen("output.txt","w",stdout)



ll dp[105][100005],w[100005],p[100005];



int main()

{

	ll n,c,i,j;

    scll(n,c);

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

    scll(w[i],p[i]);

    

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

    {

    	for(j=0;j<=c;j++)

    	{

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

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

    		else

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

		}

	}

	ll ans=0;

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

	{

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

	}

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

}
// 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.6348317333658797x):
/*Rabbi Zidni Ilma*/



#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define scl(n) scanf("%lld",&n)

#define scll(n,m) scanf("%lld%lld",&n,&m)

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define mod 1000000007

#define read freopen("input.txt","r",stdin)

#define write freopen("output.txt","w",stdout)



ll dp[105][100005],w[100005],p[100005];



int main()

{

	ll n,c,i,j;

    scll(n,c);

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

    scll(w[i],p[i]);

    

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

    {

    	for(j=0;j<=c;j++)

    	{

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

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

    		else

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

		}

	}

	ll ans=0;

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

	{

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

	}

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

using namespace std;

#define ll long long int



int sz[200005],val[200005];

ll dp[105][100005];



int main()

{

    int s,n;

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

    

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

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

    

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

    {

        for(int cap=0;cap<=s;cap++)

        {

            if(!cap || !item)

            dp[item][cap]=0LL;

            

            else if(sz[item]<=cap)

            dp[item][cap]=max(dp[item-1][cap],dp[item-1][cap-sz[item]]+(ll)val[item]);

            

            else

            dp[item][cap] = dp[item-1][cap];

        }

    }

    

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

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

using namespace std;

#define ll long long int



int sz[200005],val[200005];

ll dp[105][100005];



int main()

{

    int s,n;

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

    

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

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

    

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

    {

        for(int cap=0;cap<=s;cap++)

        {

            if(!cap || !item)

            dp[item][cap]=0LL;

            

            else if(sz[item]<=cap)

            dp[item][cap]=max(dp[item-1][cap],dp[item-1][cap-sz[item]]+(ll)val[item]);

            

            else

            dp[item][cap] = dp[item-1][cap];

        }

    }

    

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

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

using namespace std;

#define ll long long int



int sz[200005],val[200005];

ll dp[105][100005];



int main()

{

    int s,n;

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

    

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

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

    

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

    {

        for(int cap=0;cap<=s;cap++)

        {

            if(!cap || !item)

            dp[item][cap]=0LL;

            

            else if(sz[item]<=cap)

            dp[item][cap]=max(dp[item-1][cap],dp[item-1][cap-sz[item]]+(ll)val[item]);

            

            else

            dp[item][cap] = dp[item-1][cap];

        }

    }

    

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

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

using namespace std;

#define ll long long int



int sz[200005],val[200005];

ll dp[105][100005];



int main()

{

    int s,n;

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

    

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

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

    

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

    {

        for(int cap=0;cap<=s;cap++)

        {

            if(!cap || !item)

            dp[item][cap]=0LL;

            

            else if(sz[item]<=cap)

            dp[item][cap]=max(dp[item-1][cap],dp[item-1][cap-sz[item]]+(ll)val[item]);

            

            else

            dp[item][cap] = dp[item-1][cap];

        }

    }

    

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

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

using namespace std;

#define ll long long int



int sz[200005],val[200005];

ll dp[105][100005];



int main()

{

    int s,n;

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

    

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

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

    

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

    {

        for(int cap=0;cap<=s;cap++)

        {

            if(!cap || !item)

            dp[item][cap]=0LL;

            

            else if(sz[item]<=cap)

            dp[item][cap]=max(dp[item-1][cap],dp[item-1][cap-sz[item]]+(ll)val[item]);

            

            else

            dp[item][cap] = dp[item-1][cap];

        }

    }

    

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

    return 0;

}