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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

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

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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



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

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

#define trav(a,x) for (auto& a: x)

#define cout(tt) cout<<"Case #"<<(tt)<<": ";

#define minheap(name) priority_queue <int, vector<int>, greater<int> > (name); 

#define ll long long int

/*	Things to remember handling:

	1. int overflows

	2. array boundaries

	3. base cases (n=1)

*/



using namespace std;



int main(){

	ios::sync_with_stdio(0);

	cin.tie(0);

	

		int W,N;

		cin>>N>>W;

		int v[N],w[N];

		FOR(i,0,N){

			cin>>w[i];

			cin>>v[i];

		}

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

		FOR(i,1,N+1){

			FOR(j,1,W+1){

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

					int newWeight = j-w[i-1];

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

				}else

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

			}

		}

		cout<<dp[N][W]<<endl;

			

	

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

	memset(dp,0,sizeof(dp));

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

		for (int j=t;j>=1;j--)

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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



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

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

#define trav(a,x) for (auto& a: x)

#define cout(tt) cout<<"Case #"<<(tt)<<": ";

#define minheap(name) priority_queue <int, vector<int>, greater<int> > (name); 

#define ll long long int

/*	Things to remember handling:

	1. int overflows

	2. array boundaries

	3. base cases (n=1)

*/



using namespace std;



int main(){

	ios::sync_with_stdio(0);

	cin.tie(0);

	

		int W,N;

		cin>>N>>W;

		int v[N],w[N];

		FOR(i,0,N){

			cin>>w[i];

			cin>>v[i];

		}

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

		FOR(i,1,N+1){

			FOR(j,1,W+1){

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

					int newWeight = j-w[i-1];

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

				}else

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

			}

		}

		cout<<dp[N][W]<<endl;

			

	

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

using namespace std;

typedef long long ll;

const ll max_n=1e5+100;

const ll inf=0x3f3f3f3f;

ll t,n,m,p[max_n],v[max_n],q[max_n],dp[max_n];

int main(){

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

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    while(cin>>n>>m){

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

            cin>>p[i]>>q[i];

        }

        memset(dp,0,sizeof(dp));

        ll ans=0;

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

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

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

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

            }

        }cout<<ans<<endl;

    }

    return 0;

}


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



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

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

#define trav(a,x) for (auto& a: x)

#define cout(tt) cout<<"Case #"<<(tt)<<": ";

#define minheap(name) priority_queue <int, vector<int>, greater<int> > (name); 

#define ll long long int

/*	Things to remember handling:

	1. int overflows

	2. array boundaries

	3. base cases (n=1)

*/



using namespace std;



int main(){

	ios::sync_with_stdio(0);

	cin.tie(0);

	

		int W,N;

		cin>>N>>W;

		int v[N],w[N];

		FOR(i,0,N){

			cin>>w[i];

			cin>>v[i];

		}

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

		FOR(i,1,N+1){

			FOR(j,1,W+1){

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

					int newWeight = j-w[i-1];

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

				}else

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

			}

		}

		cout<<dp[N][W]<<endl;

			

	

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

using namespace std;



typedef long long ll;



const int maxn = 105, maxw = 1e5 + 5;



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

{

    ll n, W, w[maxn], v[maxn], dp[maxw] = {0};

    cin >> n >> W;

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

        scanf("%lld %lld", &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;

    return 0;

}

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



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

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

#define trav(a,x) for (auto& a: x)

#define cout(tt) cout<<"Case #"<<(tt)<<": ";

#define minheap(name) priority_queue <int, vector<int>, greater<int> > (name); 

#define ll long long int

/*	Things to remember handling:

	1. int overflows

	2. array boundaries

	3. base cases (n=1)

*/



using namespace std;



int main(){

	ios::sync_with_stdio(0);

	cin.tie(0);

	

		int W,N;

		cin>>N>>W;

		int v[N],w[N];

		FOR(i,0,N){

			cin>>w[i];

			cin>>v[i];

		}

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

		FOR(i,1,N+1){

			FOR(j,1,W+1){

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

					int newWeight = j-w[i-1];

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

				}else

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

			}

		}

		cout<<dp[N][W]<<endl;

			

	

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

const int dir[4][2] = { -1,0,1,0,0,-1,0,1 };

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

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

	f[0] = 0;

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

		int w, v;

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

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

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



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

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

#include<iomanip>

#include<cstdio>

#include<cmath>

#include<vector>

#include<string>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<limits>

#include<stack>



using namespace std;



typedef unsigned long long ll;

typedef pair<int,int> ii;

typedef vector<pair<int,int> > vii;

typedef vector<vii> vvii;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef vector<ll> vll;

typedef vector<vll> vvll;

typedef vector<bool> vb;

typedef vector<vb> vvb;

typedef vector<char> vc;

typedef vector<vc> vvc;

typedef vector<string> vs;



int INF = std::numeric_limits<int>::max();

int NINF = std::numeric_limits<int>::min();

int MOD = 1e9+7;



int col[] = {0,-1,0,1,1,1,-1,-1};

int row[] = {-1,0,1,0,1,-1,1,-1};



//knight moves

int cc[] = {1,2,2,1,-1,-1,-2,-2};

int rr[] = {-2,-1,1,2,-2,2,1,-1};



int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);



    int n, w;

    cin >> n >> w;



    vi wts(n), vals(n);

    vvll dp(n,vll(w+1,0));



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

        cin >> wts[i] >> vals[i];



    //initialize dp table

    for(int i = wts[0]; i <= w ; ++i)

        dp[0][i] = vals[0];



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

    {

        for(int j = 0; j < wts[i] ; ++j)

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



        for(int j = wts[i]; j <= w ; ++j)

        {

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

        }

    }



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

    {

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

        {

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

        }

        cout << endl;

    }*/



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

    return 0;

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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

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

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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

#include<iomanip>

#include<cstdio>

#include<cmath>

#include<vector>

#include<string>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<limits>

#include<stack>



using namespace std;



typedef unsigned long long ll;

typedef pair<int,int> ii;

typedef vector<pair<int,int> > vii;

typedef vector<vii> vvii;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef vector<ll> vll;

typedef vector<vll> vvll;

typedef vector<bool> vb;

typedef vector<vb> vvb;

typedef vector<char> vc;

typedef vector<vc> vvc;

typedef vector<string> vs;



int INF = std::numeric_limits<int>::max();

int NINF = std::numeric_limits<int>::min();

int MOD = 1e9+7;



int col[] = {0,-1,0,1,1,1,-1,-1};

int row[] = {-1,0,1,0,1,-1,1,-1};



//knight moves

int cc[] = {1,2,2,1,-1,-1,-2,-2};

int rr[] = {-2,-1,1,2,-2,2,1,-1};



int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);



    int n, w;

    cin >> n >> w;



    vi wts(n), vals(n);

    vvll dp(n,vll(w+1,0));



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

        cin >> wts[i] >> vals[i];



    //initialize dp table

    for(int i = wts[0]; i <= w ; ++i)

        dp[0][i] = vals[0];



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

    {

        for(int j = 0; j < wts[i] ; ++j)

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



        for(int j = wts[i]; j <= w ; ++j)

        {

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

        }

    }



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

    {

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

        {

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

        }

        cout << endl;

    }*/



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

    return 0;

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

	memset(dp,0,sizeof(dp));

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

		for (int j=t;j>=1;j--)

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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

#include<iomanip>

#include<cstdio>

#include<cmath>

#include<vector>

#include<string>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<limits>

#include<stack>



using namespace std;



typedef unsigned long long ll;

typedef pair<int,int> ii;

typedef vector<pair<int,int> > vii;

typedef vector<vii> vvii;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef vector<ll> vll;

typedef vector<vll> vvll;

typedef vector<bool> vb;

typedef vector<vb> vvb;

typedef vector<char> vc;

typedef vector<vc> vvc;

typedef vector<string> vs;



int INF = std::numeric_limits<int>::max();

int NINF = std::numeric_limits<int>::min();

int MOD = 1e9+7;



int col[] = {0,-1,0,1,1,1,-1,-1};

int row[] = {-1,0,1,0,1,-1,1,-1};



//knight moves

int cc[] = {1,2,2,1,-1,-1,-2,-2};

int rr[] = {-2,-1,1,2,-2,2,1,-1};



int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);



    int n, w;

    cin >> n >> w;



    vi wts(n), vals(n);

    vvll dp(n,vll(w+1,0));



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

        cin >> wts[i] >> vals[i];



    //initialize dp table

    for(int i = wts[0]; i <= w ; ++i)

        dp[0][i] = vals[0];



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

    {

        for(int j = 0; j < wts[i] ; ++j)

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



        for(int j = wts[i]; j <= w ; ++j)

        {

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

        }

    }



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

    {

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

        {

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

        }

        cout << endl;

    }*/



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

    return 0;

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

using namespace std;

typedef long long ll;

const ll max_n=1e5+100;

const ll inf=0x3f3f3f3f;

ll t,n,m,p[max_n],v[max_n],q[max_n],dp[max_n];

int main(){

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

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    while(cin>>n>>m){

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

            cin>>p[i]>>q[i];

        }

        memset(dp,0,sizeof(dp));

        ll ans=0;

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

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

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

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

            }

        }cout<<ans<<endl;

    }

    return 0;

}


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

#include<iomanip>

#include<cstdio>

#include<cmath>

#include<vector>

#include<string>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<limits>

#include<stack>



using namespace std;



typedef unsigned long long ll;

typedef pair<int,int> ii;

typedef vector<pair<int,int> > vii;

typedef vector<vii> vvii;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef vector<ll> vll;

typedef vector<vll> vvll;

typedef vector<bool> vb;

typedef vector<vb> vvb;

typedef vector<char> vc;

typedef vector<vc> vvc;

typedef vector<string> vs;



int INF = std::numeric_limits<int>::max();

int NINF = std::numeric_limits<int>::min();

int MOD = 1e9+7;



int col[] = {0,-1,0,1,1,1,-1,-1};

int row[] = {-1,0,1,0,1,-1,1,-1};



//knight moves

int cc[] = {1,2,2,1,-1,-1,-2,-2};

int rr[] = {-2,-1,1,2,-2,2,1,-1};



int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);



    int n, w;

    cin >> n >> w;



    vi wts(n), vals(n);

    vvll dp(n,vll(w+1,0));



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

        cin >> wts[i] >> vals[i];



    //initialize dp table

    for(int i = wts[0]; i <= w ; ++i)

        dp[0][i] = vals[0];



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

    {

        for(int j = 0; j < wts[i] ; ++j)

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



        for(int j = wts[i]; j <= w ; ++j)

        {

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

        }

    }



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

    {

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

        {

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

        }

        cout << endl;

    }*/



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

    return 0;

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

using namespace std;



typedef long long ll;



const int maxn = 105, maxw = 1e5 + 5;



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

{

    ll n, W, w[maxn], v[maxn], dp[maxw] = {0};

    cin >> n >> W;

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

        scanf("%lld %lld", &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;

    return 0;

}

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

#include<iomanip>

#include<cstdio>

#include<cmath>

#include<vector>

#include<string>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<limits>

#include<stack>



using namespace std;



typedef unsigned long long ll;

typedef pair<int,int> ii;

typedef vector<pair<int,int> > vii;

typedef vector<vii> vvii;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef vector<ll> vll;

typedef vector<vll> vvll;

typedef vector<bool> vb;

typedef vector<vb> vvb;

typedef vector<char> vc;

typedef vector<vc> vvc;

typedef vector<string> vs;



int INF = std::numeric_limits<int>::max();

int NINF = std::numeric_limits<int>::min();

int MOD = 1e9+7;



int col[] = {0,-1,0,1,1,1,-1,-1};

int row[] = {-1,0,1,0,1,-1,1,-1};



//knight moves

int cc[] = {1,2,2,1,-1,-1,-2,-2};

int rr[] = {-2,-1,1,2,-2,2,1,-1};



int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);



    int n, w;

    cin >> n >> w;



    vi wts(n), vals(n);

    vvll dp(n,vll(w+1,0));



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

        cin >> wts[i] >> vals[i];



    //initialize dp table

    for(int i = wts[0]; i <= w ; ++i)

        dp[0][i] = vals[0];



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

    {

        for(int j = 0; j < wts[i] ; ++j)

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



        for(int j = wts[i]; j <= w ; ++j)

        {

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

        }

    }



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

    {

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

        {

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

        }

        cout << endl;

    }*/



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

    return 0;

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

const int dir[4][2] = { -1,0,1,0,0,-1,0,1 };

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

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

	f[0] = 0;

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

		int w, v;

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

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

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



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

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

#define ll long long int

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

#define vl vector<ll>

#define vi vector<int>

#define vii vector<pair<int, int> >

const ll mod = 1e9 + 7;

const ll inf = LLONG_MAX;

using namespace std;



ll power_mod(ll x, ll y, ll p)

{

	ll ans = 1;

	x = x%p;

	if(x==0)

	return p;



	while(y>0)

	{

		if(y&1)

		{

			ans = (ans*x)%p;

		}

		y = y>>1;

		x = (x*x)%p;

	}

	return ans;

} 

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

{ 

    ll i, w; 

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

  

    // Build table K[][] in bottom up manner 

    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()

{

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	int t;

	ll n,w,i,j,k;

	cin>>n>>w;

	ll val[n], wt[n];

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

	{

	    cin>>wt[i]>>val[i];

	}

	cout<<knapSack(w, wt, val, n);

	return 0;

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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

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

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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

#define ll long long int

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

#define vl vector<ll>

#define vi vector<int>

#define vii vector<pair<int, int> >

const ll mod = 1e9 + 7;

const ll inf = LLONG_MAX;

using namespace std;



ll power_mod(ll x, ll y, ll p)

{

	ll ans = 1;

	x = x%p;

	if(x==0)

	return p;



	while(y>0)

	{

		if(y&1)

		{

			ans = (ans*x)%p;

		}

		y = y>>1;

		x = (x*x)%p;

	}

	return ans;

} 

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

{ 

    ll i, w; 

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

  

    // Build table K[][] in bottom up manner 

    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()

{

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	int t;

	ll n,w,i,j,k;

	cin>>n>>w;

	ll val[n], wt[n];

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

	{

	    cin>>wt[i]>>val[i];

	}

	cout<<knapSack(w, wt, val, n);

	return 0;

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

	memset(dp,0,sizeof(dp));

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

		for (int j=t;j>=1;j--)

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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

#define ll long long int

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

#define vl vector<ll>

#define vi vector<int>

#define vii vector<pair<int, int> >

const ll mod = 1e9 + 7;

const ll inf = LLONG_MAX;

using namespace std;



ll power_mod(ll x, ll y, ll p)

{

	ll ans = 1;

	x = x%p;

	if(x==0)

	return p;



	while(y>0)

	{

		if(y&1)

		{

			ans = (ans*x)%p;

		}

		y = y>>1;

		x = (x*x)%p;

	}

	return ans;

} 

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

{ 

    ll i, w; 

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

  

    // Build table K[][] in bottom up manner 

    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()

{

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	int t;

	ll n,w,i,j,k;

	cin>>n>>w;

	ll val[n], wt[n];

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

	{

	    cin>>wt[i]>>val[i];

	}

	cout<<knapSack(w, wt, val, n);

	return 0;

}