stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <climits>

#include <vector>



using namespace std;



#define MAXN 1000

vector<long int> table[MAXN];

vector<long int> v, w;



void initialize(int n, int w){

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

        table[i].resize(w + 1);

    }

}



long int knapsack(int n, int W) {

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

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

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

                table[i][j] = 0;

                continue;

            }

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

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

            }

            else

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

        }

    }

    return table[n][W];

}



int main() {

    long int n, W;

    cin >> n >> W;

    

    v.resize(n);

    w.resize(n);

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

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

    }

    initialize(n, W);

    cout << knapsack(n, W) << endl;

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

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

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

    //     }

    //     cout << endl;

    // }

}

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

#include <cstring>

#include <algorithm>

using namespace std;

int n,m,w,v;

long long f[100005];

int main()

{

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

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

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

		for(int j=m;j>=w;--j)

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

	}

	printf("%lld\n",f[m]);

	return 0;

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

using namespace std;

#define db(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<'\n'

const int N = 1e6;

#define ll long long



int main(){

	ios_base::sync_with_stdio(0);

	int a,b,n,W,w,val,T,cas=0;

	cin>>n>>W;

	vector<ll> dp(W+1);

	// max value in same weight

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

		cin>>w>>val;

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

			dp[weight_already+w] = max(dp[weight_already+w], dp[weight_already]+val);

		}

	}

	cout<<dp[W]<<endl;

	return 0;

}

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

#include <cstring>

#include <algorithm>

using namespace std;

int n,m,w,v;

long long f[100005];

int main()

{

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

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

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

		for(int j=m;j>=w;--j)

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

	}

	printf("%lld\n",f[m]);

	return 0;

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

using namespace std;



long int knapsack(long int W, long int wt[], long int b[], long int n) {

	// Tabela

	long int V[n + 1][W + 1];



	// inicializando a primeira linha e a primeira coluna com 0

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

		V[0][w] = 0;

	}

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

		V[i][0] = 0;

	}



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

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

			// elemento pode fazer parte da solução

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

				// max

				if((b[i - 1] + V[i - 1][w - wt[i - 1]]) > V[i - 1][w]) {

					V[i][w] = b[i - 1] + V[i - 1][w - wt[i - 1]];

				} else {

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

				}

			} else {

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

			}

		}

	}



	// Retorna o valor máximo colocado na mochila

	return V[n][W];

}



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

	// Capacidade máxima da mochila: W

	// Número de elementos: n

  long int n, W;

	cin >> n >> W;



	// Vetor com os valores (benefícios) de cada elemento: b[]

	// Vetor com os pesos de cada elemento: wt[]

  long int wt[n], b[n];

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

    cin >> wt[i] >> b[i];

  }

	// Obter o máximo valor que pode ser colocado na mochila

	long int max_value = knapsack(W, wt, b, n);



	cout << max_value << endl;



	return 0;

}

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

#include <cstring>

#include <algorithm>

using namespace std;

int n,m,w,v;

long long f[100005];

int main()

{

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

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

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

		for(int j=m;j>=w;--j)

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

	}

	printf("%lld\n",f[m]);

	return 0;

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

#include <bits/stdc++.h>

using namespace std;



int main() {

  long long n, pesoMochila;



  cin>>n>>pesoMochila;



  long long pesoItens[n], valorItens[n], mochilaDP[n+1][pesoMochila+1];



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

    cin>>pesoItens[i]>>valorItens[i];

  }

 

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

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

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

      mochilaDP[i][j] = 0;

     }else if(pesoItens[i-1] <= j){

        mochilaDP[i][j] = max(mochilaDP[i-1][j], mochilaDP[i-1][j-pesoItens[i-1]]+valorItens[i-1]);

      }else{

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

      }

    }

  }



  cout<<mochilaDP[n][pesoMochila]<<endl;



}

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

#include <cstring>

#include <algorithm>

using namespace std;

int n,m,w,v;

long long f[100005];

int main()

{

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

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

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

		for(int j=m;j>=w;--j)

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

	}

	printf("%lld\n",f[m]);

	return 0;

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

#define ll long long

#define ull unsigned ll

#define ld long double

#define pll pair<ll, ll>

#define pii pair<int, int>

#define f first

#define se second

#define pb push_back

#define ft fflush(stdout)

 

 

using namespace std;

 

 

const int N = 1e5 + 123;

const int PLS = 3e5 + 123;

const int mod = 1e9 + 7;

const ll inf = 1e16;





ll n, a[N], b[N], w, dp[110][N];





int main() {

    ios_base::sync_with_stdio(NULL);

    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> w;

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

        cin >> a[i] >> b[i];

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

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

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

            if (j >= a[i])

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

        }

    cout << dp[n][w];

}

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

#include <cstring>

#include <algorithm>

using namespace std;

int n,m,w,v;

long long f[100005];

int main()

{

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

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

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

		for(int j=m;j>=w;--j)

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

	}

	printf("%lld\n",f[m]);

	return 0;

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

 

#define int long long

//#pragma GCC optimize("Ofast")

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

 

 

#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);

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

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

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

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

#define pb push_back

#define ppb pop_back

#define mp make_pair

#define s second

#define f first

 

 

using namespace std;

 

 

typedef pair < long long, long long > pll;    

typedef pair < int, int > pii;

typedef unsigned long long ull;         

typedef vector < pii > vpii;

typedef vector < int > vi;

typedef long double ldb; 

typedef long long ll;  

typedef double db;                         

 

 

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;

const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);

const int inf = 1e9, N = 1e5 + 48, mod = 1e9 + 7, maxn = 102;

const db eps = 1e-12, pi = 3.14159265359;

const ll INF = 1e18;





int n, m, w[maxn], c[maxn], dp[N];



main () {

	cin >> n >> m;

	forn (i, 1, n)

		cin >> w[i] >> c[i];





	forn (i, 1, n)

		forev (j, m, w[i])

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



	cout << *max_element(dp + 1, dp + 1 + m);			

} 

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

#include <cstring>

#include <algorithm>

using namespace std;

int n,m,w,v;

long long f[100005];

int main()

{

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

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

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

		for(int j=m;j>=w;--j)

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

	}

	printf("%lld\n",f[m]);

	return 0;

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



#define ll long long

#define f first

#define se second

#define pb push_back

#define mp make_pair

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

#define lb lower_bound

#define ub upper_bound

#define pii pair<ll, ll>



using namespace std;



const int N = 1e5 + 100, mod = 1e9, inf = 1e9 + 7;

ll n, m, dp[N];

pii a[N];



ll bin_pow(int x, int y){

    if(y == 0)

        return 1;

    if(y == 1)

        return x;

    if(y % 2 == 0){

        ll z = bin_pow(x, y / 2);

        return (z * z) % mod;

    }

    return (bin_pow(x, y - 1) * x) % mod;

}





int main(){

    boost;

    cin >> n >> m;

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

        cin >> a[i].se >> a[i].f;

    }

    sort(a + 1, a + n + 1);

    reverse(a + 1, a + n + 1);

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

        for(int j = m; j >= 1; j--){

            if(j - a[i].se == 0 || (j - a[i].se > 0 && dp[j - a[i].se])){

                dp[j] = max(dp[j], dp[j - a[i].se] + a[i].f);

            }

        }

    }

    ll ans = 0;

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

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

    }

    cout << ans;

    return 0;

}




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

#include <cstring>

#include <algorithm>

using namespace std;

int n,m,w,v;

long long f[100005];

int main()

{

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

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

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

		for(int j=m;j>=w;--j)

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

	}

	printf("%lld\n",f[m]);

	return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

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

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.7860706648736067x):
//بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ

//لا إله إلا الله محمد رسول الله



#include <bits/stdc++.h>



#pragma GCC optimize("Ofast")



#define ll long long

#define pb push_back

#define fr first

#define sc second

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

#define out freopen("snakes.out", "w", stdout)

using namespace std;



ll n, W;

ll dp[105][100005];

ll w[100005], v[100005];

int main(){

    //in;

    //out;

    ios_base::sync_with_stdio(false);

    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 = 0; 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]);

        }

    }

    ll ans = 0;

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

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

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

        }

    }



    cout << ans;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

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

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.7657624926825364x):
// Author : Syed Mujtaba

// Seek knowledge from the Cradle to the Grave !!

// https://www.linkedin.com/in/syed-mujtaba-064a5016a 



#include <bits/stdc++.h>

using namespace std;

#define int     long long

#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

signed main()

{

	fast_io

	int n, w;

	cin >> n >> w;

	vector < int > wt(n), val(n);

	int dp[n + 1][w + 1] = {0};



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

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



	for(int i = 0; i <= w; i++) // base case

	{

		if(i >= wt[0])

			dp[1][i] = val[0];

		else

			dp[1][i] = 0;

	}

	for(int i = 2; i <= n; i++) // tabulation

	{

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

		{

			dp[i][j] = 0;

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

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

			else

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

		}

	}

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

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

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

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

using namespace std;



const int maxn = 100+5;

const int maxm = 1e5+5;



long long f[maxn][maxm];

int obj[maxn],w[maxn];

int W,n;



int main(){

	cin >> n >> W;



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

		cin >> w[i];

		cin >> obj[i];

	} 

	

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

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

			if (w[i] > j){

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

			}else{

				

				f[i][j] = max(f[i - 1][j],f[i - 1][j - w[i]] + obj[i]);

			}

		}

	}

	

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

	

	return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

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

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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



using namespace std;

const int N=200000;

int main(){

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

	long long b,maxis=-1e9,a,n,i,j,dp[N],slot;

	cin>>n>>slot;

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

		cin>>a>>b;

		for(j=slot;j>=a;--j){

			dp[j]=max(dp[j],dp[j-a]+b);

		}

	}

	for(i=0;i<=slot;++i) maxis=max(maxis,dp[i]);

	cout<<maxis;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

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

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

#include <iostream>

#include <vector>

using namespace std;



#define ill pair<int, long long >

#define ff first // Weight

#define ss second // Value



long long temp[109][100009];



int main() {

  int i, j;

  int n, W, w;

  long long v;



  vector<ill > ob;



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

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

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

    ob.push_back(make_pair(w, v));

  }



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

    for(j = 1; j <= W; j++) { // weight

      if(ob[i - 1].ff > j) temp[i][j] = temp[i - 1][j];

      else (temp[i - 1][j] > ob[i - 1].ss + temp[i - 1][j - ob[i - 1].ff]) ? temp[i][j] = temp[i - 1][j] : temp[i][j] = ob[i - 1].ss + temp[i - 1][j - ob[i - 1].ff];

    }

  }



  printf("%lld", temp[n][W]);

  return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

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

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

#include <algorithm>



int n, w;



long long arr[100005];



int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(NULL);



    std::cin >> n >> w;

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

    {

        long long a, b;

        std::cin >> a >> b;

        for(int j=w; j>a-1; j--) arr[j] = std::max(arr[j], arr[j-a]+b);

    }

    std::cout << *std::max_element(&arr[0], &arr[w+1]) << '\n';

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

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

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

using namespace std;

typedef long long int ll;

int v[1000];

ll w[1000];



ll Knapsack(int n, ll m){

    ll mem[n+1][m+1];

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

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

            if ( i == 0 || j == 0) mem[i][j] = 0;

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

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

        }

    }return mem[n][m];

}





int main(){

    int n,w2;

    cin >> n >> w2;

    for (ll i=0;i<n;i++) cin >> w[i] >> v[i];

    cout << Knapsack(n,w2);

    return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

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

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

#define ll long long

using namespace std;

const int maxn = 1e5+5;

ll dp[105][maxn], v[maxn], w[maxn];



int main(){

	int n, k; cin >> n >> k;

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

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

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

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

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

		}

	}

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

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

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

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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



using namespace std;

vector<int> a;

vector<long long> v;

int w;

int n;



long long knapsack()

{

    long long K[n+1][w+1];



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

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

    {

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

        {

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

                K[i][j] = 0;

            else if (v[i-1] <= j)

                K[i][j] = max(a[i-1] + K[i-1][j-v[i-1]],  K[i-1][j]);

            else

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

        }

    }



    return K[n][w];

}



int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    long long x, y;

    cin >> n >> w;

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

    {

        cin >> x >> y;

        v.push_back(x);

        a.push_back(y);

    }

    cout<<knapsack();



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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

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

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.8265195287245635x):
// Author : Mohamed Sameh

#include <bits/stdc++.h>

#define pb push_back

#define f first

#define s second

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

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

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

#define Flush fflush(stdout);

typedef long long ll ;

using namespace std ;

const int M = 100 ;

const int MAXW = 1e5+1; 

ll dp[M][MAXW];

int w[M],v[M];

int N , W ;

int main ()

{   

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

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

    {

        scanf ("%d%d" ,w+i , v+i); 

    }

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

        if (j >= w[0])

            dp[0][j] = v[0];

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

    {

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

        {

            // what can I take if I Have capacity = j 

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

            if (j >= w[i])

            {

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

            }

        }

    }

    printf ("%lld\n" , dp[N-1][W]); 



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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

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

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.810288280552706x):
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

using namespace std;

#define clr(arr, x) memset(arr, x, sizeof arr)

#define endl "\n"

#define Accepted 0

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vl;

const int N = 1e5 + 5;

ll dp[2][N];

int main()

{

	int n, W;

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

	vi val(n + 1), cap(n + 1);

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

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



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

		int idx = i % 2;

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

			dp[idx][j] = dp[!idx][j];

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

				dp[idx][j] = max(dp[idx][j], dp[!idx][j - cap[i]] + val[i]);

			}

		}

	}

	n--;

	printf("%lld", dp[n % 2][W]);



	return Accepted;

}