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

#include <limits.h>

#include <algorithm>  

#include <numeric>

 

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

using namespace std;

 

#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define endl '\n'

using ll = long long;

 

const int precision = 3;

const int modulo =  1000000007; // 10^9 + 7

const ll lmodulo =  1000000007; // 10^9 + 7

 

const double EPS = 1e-9;

const ll inf = 1e18;



void solve () {

	int n, W; cin >> n >> W;

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



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

		int cw, v; cin >> cw >> v;

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

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

			if(w - cw >= 0)

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

		} 

	}

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

}



// void solve () {

// 	int n, W; cin >> n >> W;

// 	vector<vector<ll>> dp(2, vector<ll>(W + 1));



// 	for (auto i = 1; i <= n; ++i) {

// 		int cw, v; cin >> cw >> v;

// 		auto & cur = dp[i % 2];

// 		const auto & prev = dp[(i - 1) % 2];

// 		for (int w = W; w >= 0; --w) {

// 			cur[w] = prev[w];

// 			if(w - cw >= 0) {

// 				cur[w] = max(cur[w], v + prev[w - cw]);

// 			}

// 		}

// 	}



// 	cout << dp[n % 2][W];

// }



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout.tie(nullptr);

  cout.precision(precision);

  cout.setf(ios_base::fixed);

  solve();

  return 0;

}




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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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

using ll = long long;

using namespace std;



int n, w;

ll dp[100100];

int val[102], wt[102];



int main() {

	cin >> n >> w;

	for (int i = 1; i <= n; ++i) cin >> wt[i] >> val[i];



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

		for (int weight = w; weight >= 0; --weight) {

			if ( weight - wt[pos] >= 0 ) 

				dp[weight] = max(dp[weight], dp[weight - wt[pos]] + val[pos]);

		}

	}



	cout << dp[w] << endl;

	return 0;

}


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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

}
// Slower C++ solution:
/*

	Author: Luis Manuel D�az Bar�n (LUISMO)

	Problem:

	Online Judge:

	Idea:

*/

#include<bits/stdc++.h>

// Types

#define ll long long

#define ull unsigned long long

// IO

#define sf scanf

#define pf printf

#define mkp make_pair

#define fi first

#define se second

#define endl "\n"



using namespace std;



typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const ll inf = 1e16 + 3;

const int mod = 1e9 + 7;

const int lim = 2e5 + 2;



ll N, W;



ll dp[lim];

ll vi[lim];

ll wi[lim];

bool mark[lim];



void solve()

{

    cin >> N >> W;



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

    {

        cin >> wi[i] >> vi[i];

    }



    ll answ = 0;



    mark[0] = true;

    for(int item = 1; item <= N; item++)

    {

        for(int w = W; w > 0; w--)

        {

            if(w - wi[item] >= 0 && mark[w - wi[item]])

            {

                dp[w] = max(dp[w], vi[item] + dp[w - wi[item]]);

                mark[w] = true;



                answ = max(answ, dp[w]);

            }

        }

    }

    cout << answ;

}



void fastIO()

{

	cin.sync_with_stdio(false);

	cin.tie(0);

}



void IO()

{

	if(fopen("d:\\lmo.in","r") != NULL)

	{

		freopen("d:\\lmo.in","r",stdin);

	}

	else if(fopen("/media/Beijing/lmo.in","r") != NULL)

	{

		freopen("/media/Beijing/lmo.in", "r", stdin);

	}

}



int main()

{

	IO();



	fastIO();



	solve();

}


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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	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: 9.403785369104176x):
#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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

#include <string>

#include <cstdlib>

using namespace std;



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

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



#define si(a)               scanf("%d", &a)

#define sii(a,b)            scanf("%d %d", &a, &b)

#define siii(a,b,c)         scanf("%d %d %d", &a, &b, &c)



#define CLR(a)              memset(a, 0, sizeof(a))

#define SET(a)              memset(a, -1, sizeof(a))



#define PI                  acos(-1.0)



#define pb                  push_back

#define mp                  make_pair

#define SORT(v)             sort(v.begin(), v.end())

#define REV(v)              reverse(v.begin(), v.end())

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

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

#define ROF(i, n)           for(int i=n-1; i>=0; i--)

#define ROF1(i, n)          for(int i=n; i>=1; i--)

#define LOOP(i, x, y)       for(int i=x; i<=y; i++)

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





typedef long long              LL;

typedef unsigned long long     ULL;

typedef vector<int>            VI;

typedef pair<int, int>         PII;

typedef pair<string, int>      PSI;

typedef pair<char, int>        PCI;



const int MAX = 100005;

const LL LMAX = 12158598925;

const double eps = 1e-9;

const int INF = 0x3f3f3f3f;



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

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

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

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



LL weight[MAX], price[MAX];



int main()

{

//    READ;

//    WRITE;

    int n, w;

    sii(n, w);

    FOR1(i, n) scanf("%lld %lld", &weight[i], &price[i]);



    LL dp[n+2][w+2];



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

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

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

            else if(weight[i] > j) dp[i][j] = dp[i-1][j];

            else{

                int p = i - 1;

                int q = j - weight[i];

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

            }

        }

    }





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



    return 0;

}


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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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

using namespace std;



#define fr(i,n) _back

#define pb	push_back

#define eb	emplace_back

#define mk	make_pair

#define fi	first

#define se	second

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<ii> vii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

const int N = 1e5 + 3;

ll dp[N];



int main() {

    ios_base::sync_with_stdio(false);

    int n,c,w,v; cin >> n >> c;

    ll ans = 0;



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

        cin >> w >> v;

        for(int j = c; j-w >= 0; j--) {

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

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

        }

    }



    cout << ans << endl;

    return 0;

}


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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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

#include <cstring>

#include <algorithm>

#include <iostream>





using namespace std;



const int MaxN = 1e5 + 5;



long long dp[MaxN];

int w[105] , W , n;

long long v[105];



int main(){

	cin >> n >> W;

	for(int i = 1; i <= n ; i++)cin >> w[i] >> v[i];

	for(int i = 1; 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: 5.243355803360713x):
#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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

using namespace std;



int main()

{

	int N, W;

	cin >> N >> W;

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

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

	{

		long long w, v;

		cin >> w >> v;

		for (long long j = W - w; j >= 1; j--)

		{

			if (dp[j] != 0)

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

		}

		dp[w] = max(dp[w], v);

	}

	cout << *max_element(dp.begin(), dp.end());

}


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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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

using ll = long long;



int main(){

	std::cin.tie(0);

	std::ios::sync_with_stdio(false);



	int N, W;

	std::cin >> N >> W;

	std::vector<ll> V(N), wei(N), dp(W+1, 0);

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

		std::cin >> wei[i] >> V[i];

	}

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

		for(int w=W; w >= wei[i]; w--){

			dp[w] = std::max( dp[w], dp[w-wei[i]] + V[i] );

		}

	}

	std::cout << dp[W] << '\n';

	return 0;

}

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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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



using namespace std;



int n_itens, capacidade;



long long valores[101][3];



long long inventario[100001][101];



int main(){

    cin >> n_itens >> capacidade;



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

        cin >> valores[i][1];

        cin >> valores[i][2];

    }



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

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

            inventario[i][j] = 0;

        }

    }



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

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

            long long custoAnterior = inventario[j][i - 1];



            long long custoItem = 0;



            if(j - valores[i][1] >= 0){

                 custoItem = valores[i][2] + inventario[j - valores[i][1]][i - 1];

            }



            long long maximo = max(custoAnterior, custoItem);



            inventario[j][i] = maximo;

        }

    }



    cout << inventario[capacidade][n_itens] << endl;



    return 0;

}

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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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

#define int2 long long int



using namespace std;



int main(){

	int2 N, W;

	scanf("%lld%lld", &N, &W);



	pair<int2, int2> v[N];

	vector<vector<int2> > problem, itens;

	problem.resize(W+1);

	itens.resize(W+1);



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

		problem[i].resize(N+1);

		itens[i].resize(N+1);

		for(int2 j=0; j<N+1; j++){

			problem[i][j] = itens[i][j] = 0;

		}

	}



	for(int2 i=0; i<N+1; i++){

		scanf("%lld%lld", &v[i].first, &v[i].second);

	}





	for(int2 i=1; i<N+1; i++){

		for(int2 j=1; j<W+1; j++){

			int2 aceitaItem=-1, recusaItem;

			if(j-v[i-1].first>=0){

				aceitaItem = v[i-1].second + problem[j-v[i-1].first][i-1];

			}

			recusaItem = problem[j][i-1];

			problem[j][i] = max(aceitaItem, recusaItem);

		}

	}

	

	printf("%lld\n", problem[W][N]);

}

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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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

using namespace std;

#define int long long int



int n;

int w;

vector<int> weight, value;

vector< vector<int> > dp;



main(){

	

	cin >> n >> w;

	

	weight.resize(n+1);

	value.resize(n+1);



	dp.resize(n+1, vector<int>(w+1));



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

		cin >> weight[i] >> value[i];

	}



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

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

			if(i - weight[j] >= 0){

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

			}

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

		}

	}



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

}



/*



knapp(k, w) = valor max do subproblema com os k primeiros elementos e peso maximo de w



knapp(k, w) = max(knapp(k-1, w - peso[k]), knapp(k-1, w));



*/

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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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



using namespace std;



#define INF (1ll << 62)

#define pb push_back

#define ii pair<int,int>

#define OK cerr <<"OK"<< endl

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

#define ff first

#define ss second

#define int long long

#define tt tuple<int, int, int>

#define endl '\n'



int dp[105][100005]; 

int moc(int q,int p,vector<ii> vec) {

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

  {

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

      if(j >= vec[i-1].ff)

        dp[i][j] = max(dp[i-1][j],vec[i-1].ss + dp[i-1][j-vec[i-1].ff]);

      else 

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

    }

  }

  return dp[q][p];

}

signed main(signed argc, char *argv[])

{

  ios_base::sync_with_stdio(false);

  cin.tie(NULL);

  int p,q;

  vector<ii> vec;

  cin >> q >> p;

  int x,y;

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

       cin >> x >> y;

       vec.push_back(make_pair(x,y)); 

  }

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

    dp[0][i] = 0;

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

    dp[i][0] = 0;

  sort(vec.begin(),vec.end());

  cout << moc(q,p,vec) << endl;

}




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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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

 

#define ll long long

#define X first

#define Y second

#define MP make_pair

#define ld long double

 

using namespace std;

 

const int N = 5e5 + 123;

const ll mod = 1e9 + 7;



ll dp[N], res, was[N];

int n, maxw;



int main (){

	ios::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);



	cin >> n >> maxw;



	was[0] = 1;

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

		ll x, y;

		cin >> x >> y;

		for(int j = maxw;j >= x;j--){

			if(!was[j - x])

				continue;

			dp[j] = max(dp[j], dp[j - x] + y);

			was[j] = 1;

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

		}

	}

	cout << res;

}

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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

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



#define Solved int main()

#define pb push_back

#define mp make_pair

#define F first

#define S second

#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

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

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

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

#define pii pair<int, int>

#define ll long long

#define ull unsigned long long

#define ld long double

#define mii map<int, int>

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

#define lb lower_bound

#define ub upper_bound

using namespace std;



inline ll bip(ll x,ll n,ll mod){ll res=1;while(n){if(n&1){res=(res*x)%mod;}x=(x*x)%mod;n>>=1;}return res;}



const int maxn = 1e9;

const ll inf = 1e18;

const int mod = 998244353;

//const int mod = 1e9 + 7;

const int N = 1e5 + 10;



int n, W, w[101], v[101];

ll dp[101][N];



void solve() {

    cin >> n >> W;



    forn (i, n)

        cin >> w[i] >> v[i];//, dp[i][w[i]] = v[i];



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

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

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

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

        }

    }



    cout << dp[n][W];



}



Solved {

    SpeedForce;

	int tt = 1;

    //cin >> tt;

	while (tt--) {

		solve();

		cout << '\n';

	}



}


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

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

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

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

				val[j+w]=max(val[j+w],val[j]+v);

			}

		}

	}

	ans=0;

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

		ans=max(ans,val[i]);

	}

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

	return 0;

}