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

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n, w;

ll **mem;

pair<int, ll> *x;

ll nap(int i = 0, int rem = w)

{

    if(i == n)

        return 0;

    if(~mem[i][rem])

        return mem[i][rem];

    ll first = nap(i + 1, rem), second = 0;

    if(rem >= x[i].first)

        second = x[i].second + nap(i + 1, rem - x[i].first);

    return mem[i][rem] = max(first, second);

}

int main()

{

    //cin.tie(NULL); cout.tie(NULL);  ios_base::sync_with_stdio(false);

    #ifndef ONLINE_JUDGE

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

        //freopen("out.txt", "w", stdout);

    #endif

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

    mem = new ll*[n];

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

    {

        mem[i] = new ll[w + 1];

        memset(mem[i], -1, (w + 1) * 8);

    }

    x = new pair<int, ll>[n];

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

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

    printf("%lld", nap());

}


// Faster C++ solution for the same problem (measured speedup: 5.175029481864452x):
#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 <algorithm>



// 0 for Weight index, 1 for Value index

long long arr[101][2];



// The first for Weight, the second for Value

// Notice that all the table is initialized to zero,

// because it's defined in global scope.

// Let's benefit from that.

long long table[100002][101];



int main()

{

	int n, w;

	std::cin >> n >> w;

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

		std::cin >> arr[i][0] >> arr[i][1];

	// It sets the initial row.

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

	{

		if (arr[0][0] <= i)

			table[i][0] = arr[0][1];

	}

	// The outer loop for the elements.

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

	{

		// the inner loop for the weight.

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

		{

			if (arr[j][0] > i)

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

			else

				table[i][j] = std::max(table[i][j - 1], static_cast<long long>(arr[j][1]) + table[i - arr[j][0]][j - 1]);

		}

	}

	std::cout << table[w][n - 1] << '\n';

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.238773145272892x):
#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;

typedef long long ll;

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

#define x first

#define y second



vector<vector<int>> dp, arr;

int main() {

    fast;

    int n, w;

    cin>>n>>w;

    vector<int> weight(n), value(n);

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

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

    }

    ll dp[n+1][w+1];

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

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

            if(i == 0 || j == 0)

                dp[i][j] = 0;

            else{

                ll leave = dp[i-1][j], take = -1;

                if(weight[i-1] <= j)

                    take = dp[i - 1][j - weight[i-1]] + value[i-1];

                dp[i][j] = max(take, leave);

            }



        }

    }

    cout<<dp[n][w];

}

// Faster C++ solution for the same problem (measured speedup: 5.30602540627982x):
#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 Joe ios::sync_with_stdio(0); cin.tie(NULL); ios_base::sync_with_stdio(0); cout.tie(NULL);

#define INF 1e9+7

const long long N =1e5+5;

using namespace std;

int main(){

	Joe

	int n,w;

	cin>>n>>w;

	long long weight[n+5],price[n+5];

	long long arr[n+5][w+5];

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

		cin>>weight[i];

		cin>>price[i];

	}

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

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

			if(r==0||w==0)

				arr[r][c]=0;

			else if(weight[r]<=c)

				arr[r][c]=max(arr[r-1][c],price[r]+arr[r-1][c-weight[r]]);

			else

				arr[r][c]=arr[r-1][c];

		}

	}

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

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.3114161670215205x):
#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()

{

  ios::sync_with_stdio(0);cin.tie(0);ios_base::sync_with_stdio(0);

  int n,c;

  cin>>n>>c;

  int val[n+1],w[n+1];

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

    cin>>w[i]>>val[i];

    long long dp[n+5][c+5];

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

        dp[0][j]=0;

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

  {

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

      {

          if(j==0)

            dp[i][j]=0;

          else if(w[i]<=j)

          {

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

          }

          else

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

      }

  }

  cout<<dp[n][c];

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.294729504806969x):
#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 ll long long

#define pb push_back

#define F first

#define S second

const int mod = 1e9+7, A = 1e2+5;

int n, w, weight[A], val[A];

ll dp[A][100005];

ll build()

{

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

	{

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

		{

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

			

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

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

			

			dp[i][j] = ret;

		}

	}

	return dp[n][w];

}



int main()

{

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

	cin >> n >> w;

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

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

	cout << build();

	return 0;

}

	/*



	states : indx , weight



	base case : dp[0][ay 7aga] = 0, dp[ay 7aga][0] = 0



	transitions : dp[i][j] = dp[i-1][j]  |  dp[i-1][j-w] + val



	0   0



	3   30

		

	4   50

	

	5   60

	

	

	 */


// Faster C++ solution for the same problem (measured speedup: 5.294631597252159x):
#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 lp(i,n) for(int i=0; i<n; i++)

#define pb push_back

const long double pi=3.141592654;

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

using namespace std;



const ll inf = 1e9 +5, mod = 1e9+7,N = 1e5+5;



    int val[N],weights[N];

    ll dp[102][N];

int main()

{

    OSOS

	ll n,w;

    cin>>n>>w;



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

    	cin>>weights[i]>>val[i];



    for(int rem = 1; rem <= w; rem++)

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

    	{

    		ll op1,op2;

    		op1 = dp[item-1][rem];

    		op2 = 0;

    		if(rem >= weights[item])

    		{

    			op2 = val[item] + dp[item-1][rem - weights[item]];

    		}

    		dp[item][rem] = max(op1,op2);

    	}



    cout<<dp[n][w];



    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.303859749619695x):
#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:
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

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

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

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

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

#define clr(v, d) memset(v, d, sizeof(v))

#define fi first

#define se second

#define pp push_back

#define pb pop_back

#define pi 3.141592654

#define MOD 1000000007 

#define cons1 1e12

#define cons2 1e6

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int, ll> pa;

typedef unsigned long long int ull;

typedef double long dl;

const int N = 1e5+9,oo=-1e9;

ll dp[109][N], n, v[109][109];

ll sol(int i, int k){

	if (n-i&&!dp[i][k]) {

		if (k >= v[i][0])   

			dp[i][k] = v[i][1] + sol(i + 1, k - v[i][0]);

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

	}



	return dp[i][k];

}

void solve() {

	int w;

	cin >> n >> w;

	rep(i, 0, n)

		cin >> v[i][0] >> v[i][1];

	cout << sol(0, w) << endl;

}

int main() {

	ios::sync_with_stdio(0);

	cin.tie(NULL);

	cout.tie(NULL);

	int t = 1;

	//cin >> t;

	while (t--)

		solve();



#ifndef ONLINE_JUDGE

	- system("pause");

#endif



}

// Faster C++ solution for the same problem (measured speedup: 5.326549460120207x):
#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 ull unsigned long long

#define ll long long

#define pb push_back

#define endl '\n'

#define line cout<<"----------------------"<<endl

#define mp make_pair

#define mod 1000000007

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)

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

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

using namespace std;

const ll  mx=300009;

vector<pair<ll ,ll > > v;

ll  dp[100001][109];

int main()

{

    ll  n,w;

    cin>>n>>w;

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

    {

        ll  a,b;

        cin>>a>>b;

        v.pb(mp(a,b));

    }

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

    {



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

        {

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

            if(v[j].first>i) continue;

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

        }

    }

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

}

/*

3 5

3 3

4 2

2 4

*/


// Faster C++ solution for the same problem (measured speedup: 5.2406845345518684x):
#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: 1.79126788814466x):
#include <bits/stdc++.h>

using namespace std;



#define ll long long

#define INF 1e9

#define fi first

#define se second



typedef vector <int> vi;

typedef pair <int, int> ii;



int main() {

    int n, w;

    cin >> n >> w;



    ii v[n+1];

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

		scanf("%d%d", &v[i].fi, &v[i].se);

	}

	// for (ii p : v) cout << p.fi << " " << p.se << endl;



    ll dp[n+1][w+1];

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



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

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

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

			if (j >= v[i].fi) {

				dp[i][j] = max(dp[i][j], dp[i-1][j-v[i].fi] + v[i].se);

			}

		}

    }



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

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

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

	// 	}

	// 	cout << endl;

	// }



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

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

using namespace std;



#define ll long long

#define INF 1e9

#define fi first

#define se second



typedef vector <int> vi;

typedef pair <int, int> ii;



int main() {

    int n, w;

    cin >> n >> w;



    ii v[n+1];

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

		scanf("%d%d", &v[i].fi, &v[i].se);

	}

	// for (ii p : v) cout << p.fi << " " << p.se << endl;



    ll dp[n+1][w+1];

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



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

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

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

			if (j >= v[i].fi) {

				dp[i][j] = max(dp[i][j], dp[i-1][j-v[i].fi] + v[i].se);

			}

		}

    }



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

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

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

	// 	}

	// 	cout << endl;

	// }



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



using namespace std;

long long cost[100000][101], w[101], v[101];



long long solve(int W, int n) {

	if(n == 0 || W == 0)

		return 0;

	if(cost[W][n] != -1)

		return cost[W][n];



	if(w[n] > W) {

		cost[W][n] = solve(W, n - 1);

		return cost[W][n];

	}

	cost[W][n] = max(solve(W - w[n], n - 1) + v[n], solve(W, n - 1));

	return cost[W][n];

}



int main() {

	int W, n;

	cin >> n >> W;

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

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



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

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

			cost[i][j] = -1;

	}



	solve(W, n);

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

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



using namespace std;

long long cost[100000][101], w[101], v[101];



long long solve(int W, int n) {

	if(n == 0 || W == 0)

		return 0;

	if(cost[W][n] != -1)

		return cost[W][n];



	if(w[n] > W) {

		cost[W][n] = solve(W, n - 1);

		return cost[W][n];

	}

	cost[W][n] = max(solve(W - w[n], n - 1) + v[n], solve(W, n - 1));

	return cost[W][n];

}



int main() {

	int W, n;

	cin >> n >> W;

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

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



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

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

			cost[i][j] = -1;

	}



	solve(W, n);

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

	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.774756016135878x):
																//  SMOKE SHISHA PLAY FIFA  // 

#include<bits/stdc++.h>

using namespace std;



typedef long long int ll;

typedef long double ld;



#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);

#define pll pair<ll,ll>

#define MP make_pair

#define ff first

#define ss second

#define PB push_back

#define mod 1000000007

#define lp(i,start,end) for(ll i=start;i<=end;i++) 

#define deb1(a) cout<<#a<<" = "<<(a)<<endl;

#define deb2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;

#define deb3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;





ll modu(ll a, ll b)

{

	ll ans =1;

	while(b>0)

	{

		if(b&1)

		ans = (ans*a)%mod;

		b/=2;

		a = (a*a)%mod;

	}

	return ans;

}



int main()

{

	fastio

	ll t=1;

	//cin >> t;

	while(t--)

	{

		ll n,m;

		cin>>n>>m;

		ll w[n+1],v[n+1];

		lp(i,1,n)

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

		ll dp[m+1];

		lp(i,1,m)

			dp[i]=-1;

		dp[0]=0;

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

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

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

			}

		} 

		ll ans=0;

		lp(i,1,m)

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

		cout<<ans<<endl;

	}

	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.2917662840458395x):
																//  SMOKE SHISHA PLAY FIFA  // 

#include<bits/stdc++.h>

using namespace std;



typedef long long int ll;

typedef long double ld;



#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);

#define pll pair<ll,ll>

#define MP make_pair

#define ff first

#define ss second

#define PB push_back

#define mod 1000000007

#define lp(i,start,end) for(ll i=start;i<=end;i++) 

#define deb1(a) cout<<#a<<" = "<<(a)<<endl;

#define deb2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;

#define deb3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;





ll modu(ll a, ll b)

{

	ll ans =1;

	while(b>0)

	{

		if(b&1)

		ans = (ans*a)%mod;

		b/=2;

		a = (a*a)%mod;

	}

	return ans;

}



int main()

{

	fastio

	ll t=1;

	//cin >> t;

	while(t--)

	{

		ll n,m;

		cin>>n>>m;

		ll w[n+1],v[n+1];

		lp(i,1,n)

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

		ll dp[m+1];

		lp(i,1,m)

			dp[i]=-1;

		dp[0]=0;

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

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

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

			}

		} 

		ll ans=0;

		lp(i,1,m)

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

		cout<<ans<<endl;

	}

	return 0;	

}