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

using namespace std;

long long dp[100005];

int main(){

    memset(dp, -1, sizeof(dp));

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

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

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

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

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

}

// Faster C++ solution for the same problem (measured speedup: 1.7764751675909285x):
#include <iostream>

#include <unordered_map>

#include <vector>

#include <stack>

#include <algorithm>

#include <list>

#include <set>

#include <climits>

#include <cmath>

#define lli long long int

using namespace std ;



lli eval(vector<lli> &weight, vector<lli> &val, vector<vector<lli> > &dp, int ind, lli w)

{

	if(ind < 0 && w < 0) return INT_MIN ;

	if(ind < 0) return 0 ;

	if(w < 0) return INT_MIN ; 



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



	dp[ind][w] = INT_MIN ;



	lli dtake = eval(weight,val,dp,ind-1,w) ;

	lli take = eval(weight,val,dp,ind-1,w - weight[ind]) ;



	if(take != INT_MIN) take+= val[ind] ;



	return dp[ind][w] = max(take,dtake) ;



}



int main(int argc, char const *argv[])

{

	lli n,w ;

	cin>>n>>w ;



	vector<lli> weight(n),val(n) ;

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

	{

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

	}



	vector<vector<lli> > dp(n,vector<lli> (w+1,-1)) ;

	cout<<eval(weight,val,dp,n-1,w)<<endl ;

	return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

		for (ULL j = w; j >= W[i]; j--)

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

using namespace std;



typedef long long int ll;

typedef pair<int,int> pi;

priority_queue<pi, vector<pi>, greater<pi> > pq; //min heap



ll mini(ll a,ll b){	return a<b?a:b;}

ll maxi(ll a,ll b){	return a>b?a:b;}

ll gcd(ll a,ll b){	if(b == 0)	return a;return gcd(b,a%b);}

ll binpow(ll n,ll x){	ll ans = 1;while(x){if(x & 1)	ans *= n;n *= n;x >>= 1;}return ans;}



int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);



    ll n,w;

    cin>>n>>w;

    

    vector<ll> dp[n+1];

    for(ll i=0;i<=n;++i)    dp[i].resize(w+1,0);



    ll row[n+1][2];

    row[0][0] = row[0][1] = 0;

    for(ll i=1;i<=n;++i)    cin>>row[i][0]>>row[i][1];



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

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

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

            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;

long long dp[100005];

int main(){

    memset(dp, -1, sizeof(dp));

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

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

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

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

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

}

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

using namespace std;



typedef long long int ll;

typedef pair<int,int> pi;

priority_queue<pi, vector<pi>, greater<pi> > pq; //min heap



ll mini(ll a,ll b){	return a<b?a:b;}

ll maxi(ll a,ll b){	return a>b?a:b;}

ll gcd(ll a,ll b){	if(b == 0)	return a;return gcd(b,a%b);}

ll binpow(ll n,ll x){	ll ans = 1;while(x){if(x & 1)	ans *= n;n *= n;x >>= 1;}return ans;}



int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);



    ll n,w;

    cin>>n>>w;

    

    vector<ll> dp[n+1];

    for(ll i=0;i<=n;++i)    dp[i].resize(w+1,0);



    ll row[n+1][2];

    row[0][0] = row[0][1] = 0;

    for(ll i=1;i<=n;++i)    cin>>row[i][0]>>row[i][1];



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

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

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

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

        }

    }



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



    return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

		for (ULL j = w; j >= W[i]; j--)

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

#define ll long long

#define pb push_back

#define mp make_pair

#define modulo 1000000007

#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

using namespace std;

int main(){

	fast_io;

	ll n,W;

	cin>>n>>W;

	ll w[n];

	ll v[n];

	ll earlier[W+1],now[W+1];

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

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

	}

	if(n==1){

		cout<<v[0]<<"\n";

		return 0;

	}

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

		earlier[i]=now[i]=-1;

	}

	earlier[0]=0;

	earlier[w[0]]=v[0];

	ll ans=0;

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

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

			if(j>=w[i] && earlier[j-w[i]]!=-1)

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

		}

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

			earlier[j]=max(earlier[j],now[j]);

			now[j]=-1;

			if(i==(n-1))

				ans=max(ans,earlier[j]);

		}

	}

	cout<<ans<<"\n";

	return 0;

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

using namespace std;

long long dp[100005];

int main(){

    memset(dp, -1, sizeof(dp));

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

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

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

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

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

}

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

#define ll long long

#define pb push_back

#define mp make_pair

#define modulo 1000000007

#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

using namespace std;

int main(){

	fast_io;

	ll n,W;

	cin>>n>>W;

	ll w[n];

	ll v[n];

	ll earlier[W+1],now[W+1];

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

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

	}

	if(n==1){

		cout<<v[0]<<"\n";

		return 0;

	}

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

		earlier[i]=now[i]=-1;

	}

	earlier[0]=0;

	earlier[w[0]]=v[0];

	ll ans=0;

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

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

			if(j>=w[i] && earlier[j-w[i]]!=-1)

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

		}

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

			earlier[j]=max(earlier[j],now[j]);

			now[j]=-1;

			if(i==(n-1))

				ans=max(ans,earlier[j]);

		}

	}

	cout<<ans<<"\n";

	return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

		for (ULL j = w; j >= W[i]; j--)

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.543773724190047x):
#include <iostream>

#include <vector>

using namespace std;



int main()

{

    ios::sync_with_stdio(false);

    int n,w;

    cin >> n >> w;

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

    long long int ans = 0;

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

        cin >> v[i].first >> v[i].second;

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

    

    // first = weight & second = value

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

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

            if(j<v[i-1].first)

                dp2[j] = dp1[j];

            else

                dp2[j] = max(dp1[j],dp1[j-v[i-1].first]+v[i-1].second);

        }

        dp1 = dp2;

    }

    cout << dp2[w] << "\n";

    

    return 0;

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

using namespace std;

long long dp[100005];

int main(){

    memset(dp, -1, sizeof(dp));

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

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

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

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

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

}

// Faster C++ solution for the same problem (measured speedup: 1.755571226079246x):
#include <iostream>

#include <vector>

using namespace std;



int main()

{

    ios::sync_with_stdio(false);

    int n,w;

    cin >> n >> w;

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

    long long int ans = 0;

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

        cin >> v[i].first >> v[i].second;

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

    

    // first = weight & second = value

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

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

            if(j<v[i-1].first)

                dp2[j] = dp1[j];

            else

                dp2[j] = max(dp1[j],dp1[j-v[i-1].first]+v[i-1].second);

        }

        dp1 = dp2;

    }

    cout << dp2[w] << "\n";

    

    return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

		for (ULL j = w; j >= W[i]; j--)

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

using namespace std;



#define MAX 100005



struct Item{

    int w;

    int v;

}item[105];



int N, W;

long long dp[105][MAX];

long long m;



int main(){

    cin>>N>>W;

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

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

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

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

            if(item[i].w+j<=W){

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

                m = max(dp[i+1][item[i].w+j], m);

            }

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

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

        }

    }

    cout<<m<<"\n";

    return 0;

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

using namespace std;

long long dp[100005];

int main(){

    memset(dp, -1, sizeof(dp));

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

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

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

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

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

}

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

using namespace std;



#define MAX 100005



struct Item{

    int w;

    int v;

}item[105];



int N, W;

long long dp[105][MAX];

long long m;



int main(){

    cin>>N>>W;

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

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

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

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

            if(item[i].w+j<=W){

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

                m = max(dp[i+1][item[i].w+j], m);

            }

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

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

        }

    }

    cout<<m<<"\n";

    return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

		for (ULL j = w; j >= W[i]; j--)

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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



#define fst first

#define snd second

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

#define pb push_back

#define ALL(s) s.begin(),s.end()

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

#define SZ(s) int(s.size())

#define DBG(x) cerr <<#x << " = " << (x) << "\n"



#define SQR(x) ((x) * (x))



#define PI 3.1415926535897932385

#define INF 1000111222

#define eps 1e-7

#define maxN 11



using namespace std;



typedef long long ll;

typedef vector<ll> vll;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

typedef vector<string> vstr;

typedef vector<vll> vvll;

typedef vector<bool> vbool;

typedef vector<pll> vpll;

typedef vector<vpll> vvpll;

typedef vector<vbool> vvbool;



int main(){FIN



	ll n,w,wi,vi;

	

	cin >> n >> w;

	vll dp(w+1);

	

	fore(i,0,n){

		cin >> wi >> vi;

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

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

	}

	ll ans = 0;

	fore(i,0,w+1)ans = max(ans,dp[i]);

	cout << ans << "\n";

	return 0;

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

using namespace std;

long long dp[100005];

int main(){

    memset(dp, -1, sizeof(dp));

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

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

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

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

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

}

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



#define fst first

#define snd second

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

#define pb push_back

#define ALL(s) s.begin(),s.end()

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

#define SZ(s) int(s.size())

#define DBG(x) cerr <<#x << " = " << (x) << "\n"



#define SQR(x) ((x) * (x))



#define PI 3.1415926535897932385

#define INF 1000111222

#define eps 1e-7

#define maxN 11



using namespace std;



typedef long long ll;

typedef vector<ll> vll;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

typedef vector<string> vstr;

typedef vector<vll> vvll;

typedef vector<bool> vbool;

typedef vector<pll> vpll;

typedef vector<vpll> vvpll;

typedef vector<vbool> vvbool;



int main(){FIN



	ll n,w,wi,vi;

	

	cin >> n >> w;

	vll dp(w+1);

	

	fore(i,0,n){

		cin >> wi >> vi;

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

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

	}

	ll ans = 0;

	fore(i,0,w+1)ans = max(ans,dp[i]);

	cout << ans << "\n";

	return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

		for (ULL j = w; j >= W[i]; j--)

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

#define INF INT_MAX

#define MINF INT_MIN

#define ll long long

#define PB push_back 

#define PF push_front

#define P_F pop_front

#define P_B pop_back

#define F front

#define B back

#define MP make_pair

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

#define forit(i, s) for(__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)

#define foritr(i, s) for(__typeof ((s).rend ()) i = (s).rbegin (); i != (s).rend (); ++i)

 

using namespace std;



int main() {

  ll n, wei;

  cin >> n >> wei;

  ll dp[n][wei+1];

  vector<int> pesos(n), valores(n);

  

  FOR(i, 0, n)

    cin >> pesos[i] >> valores[i];

    

  FOR(i, 0, wei+1){

    if(pesos[0] <= i)

      dp[0][i] = valores[0];

    else

      dp[0][i] = 0;

  }

  

  FOR(i, 1, n){

    FOR(j, 0, wei+1){

      if(pesos[i] <= j){

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

      }else

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

    }

  }

  

  cout << dp[n-1][wei] << "\n";



  return 0;

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

using namespace std;

long long dp[100005];

int main(){

    memset(dp, -1, sizeof(dp));

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

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

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

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

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

}

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

#define INF INT_MAX

#define MINF INT_MIN

#define ll long long

#define PB push_back 

#define PF push_front

#define P_F pop_front

#define P_B pop_back

#define F front

#define B back

#define MP make_pair

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

#define forit(i, s) for(__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)

#define foritr(i, s) for(__typeof ((s).rend ()) i = (s).rbegin (); i != (s).rend (); ++i)

 

using namespace std;



int main() {

  ll n, wei;

  cin >> n >> wei;

  ll dp[n][wei+1];

  vector<int> pesos(n), valores(n);

  

  FOR(i, 0, n)

    cin >> pesos[i] >> valores[i];

    

  FOR(i, 0, wei+1){

    if(pesos[0] <= i)

      dp[0][i] = valores[0];

    else

      dp[0][i] = 0;

  }

  

  FOR(i, 1, n){

    FOR(j, 0, wei+1){

      if(pesos[i] <= j){

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

      }else

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

    }

  }

  

  cout << dp[n-1][wei] << "\n";



  return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

		for (ULL j = w; j >= W[i]; j--)

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

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

#define ii          pair<int,int>

#define F           first

#define S           second

#define pb          push_back

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

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

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

#define forr(i,a)   for(int i = a; i >= 0; i--)

#define fori(i,m)   for(auto i = m.begin(); i != m.end(); i++) 

#define w(t)        while(t--)

#define sz(s)       int(s.size())

#define cls(a,car)  memset(a,car,sizeof (a))

#define db(x)       cerr << #x << " is " << x << '\n'

#define FL          freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout);

#define EjecuteTime cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"

#define angle(x)    double(x * acos(-1) / 180.0)

using namespace std;

typedef long long   ll;

typedef vector<int> vi;

typedef vector<ii>  vii;

const int N = 1 * 1e5 + 5;

const ll mod = 1e9 + 7;

const double E = 1e-9;

//int dx[] = {1, 0}, dy[] = {0, 1};

//int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

//int dx[] = {2, 1, -1, -2, -2, -1, 1, 2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

//int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy[] = {0 ,1, 1, 1, 0, -1, -1, -1};

// fflush(stdout)

// cout << flush

// a + b = a ^ b + 2 * (a & b)

int n, W;

int w[101], v[101];

ll dp[2][N];

ll f(int i, int cost){

    if(cost < 0)

        return -1e18;

    if(i == n)

        return 0;

    ll &ans = dp[i][cost];

    if(ans == -1){

        ans = max(f(i + 1, cost), f(i + 1, cost - w[i]) + v[i]);

    }return ans;

}

int main(){

    //FL;

    FIN;

    //optimizando memoria

    cin >> n >> W;

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

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

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

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

            ll &ans = dp[i & 1][cost];    

            if(i == n){

                ans = 0;

                continue;

            }

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

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

                ans = max(ans, dp[(i + 1) & 1][cost - w[i]] + v[i]);

        }

    }

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

    EjecuteTime;

    return 0;

}