stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



#define pb push_back

#define mp make_pair

#define fi first

#define se second

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

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

#define MAX 1000000

//3

typedef long long ll;

typedef pair<int,int> pii;

priority_queue< int > pq;

priority_queue< int , vector<int> , greater<int> > rpq;

set<int>s;

set <int > :: iterator itr; 

vector<int> vec[1001];

int r,n,m,inp,tc;

int arr[1000007]= {};

int w;

ll dp[107][100100];

ll solve(ll cost[], ll weight[]){

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

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

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

			else{

				if(weight[i] <= j){

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

				} 

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

			}

		}

	}

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

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

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

//		}

//		cout<<endl;

//	}

	return dp[n][w];

}



int main()

{

	cin>>n>>w;

	ll cost[n+7],weight[w+7];

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

		cin>>weight[i]>>cost[i];

	}

	cout<<solve(cost,weight)<<endl;

	return 0;

}



//65 900 17 13

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

int main(){

  long long n, m;

  cin>>n>>m;

  long long M[n+1][m+1];

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

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

      M[i][j]=0;

    }

  }

  long longresult=0;

  vector<long long>peso;

  vector<long long>valor;

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

    long long a,b;

    cin>>a>>b;

    peso.push_back(a);

    valor.push_back(b);

  }

  for(long long j=1;j<=m;j++){

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

      if(j >= peso[i-1])

        M[i][j]=max(M[i-1][j], valor[i-1]+M[i-1][j-peso[i-1]]);



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

      }

  }

  cout<<M[n][m]<<endl;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

    // }

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;



}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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];

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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);			

} 

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}




// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int maxn = 1e5 + 9;

inline int read()

{

    int data = 0, f = 1;

    char ch = getchar();

    while (!isdigit(ch))

    {

        if (ch == '-')

            f = -1;

        ch = getchar();

    }

    while (isdigit(ch))

    {

        data = (data << 3) + (data << 1) + ch - '0';

        ch = getchar();

    }

    return f * data;

}

int p[109], v[109];

ull dp[maxn];

int main()

{

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

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

    //std::ios::sync_with_stdio(false);

    //std::cin.tie(0);

    int n = read(), w = read();

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

        p[i] = read(), v[i] = read();

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

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

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

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

    //fclose(stdin);

    //fclose(stdout);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
//01背包 

#include<bits/stdc++.h>

using namespace std;



const int N = 105;

long long f[100050];//滚动数组

long long v[N];//价值

int w[N];//重量

int n,m;

 

int main()

{

 	cin>>n;//物品种数

	cin>>m;//背包容量

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

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

	}

	

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

	for(int i = 1;i<=n;++i){//外层循环物品个数 

		for(int j = m;j>=w[i];--j){//内层循环背包体积 (从大到小循环） 

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

		}

	}

	cout<<f[m]<<endl;

	return 0;

} 

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int maxn = 1e5 + 9;

inline int read()

{

    int data = 0, f = 1;

    char ch = getchar();

    while (!isdigit(ch))

    {

        if (ch == '-')

            f = -1;

        ch = getchar();

    }

    while (isdigit(ch))

    {

        data = (data << 3) + (data << 1) + ch - '0';

        ch = getchar();

    }

    return f * data;

}

int p[109], v[109];

ull dp[maxn];

int main()

{

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

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

    //std::ios::sync_with_stdio(false);

    //std::cin.tie(0);

    int n = read(), w = read();

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

        p[i] = read(), v[i] = read();

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

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

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

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

    //fclose(stdin);

    //fclose(stdout);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100+5;

const int maxw = 1e5+5;

long long dp[maxw];

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

{

	int n, w;

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

	

	memset(dp, 0, sizeof dp);

	int x, v;

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

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

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

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

		}

	}



	printf("%lld\n", dp[w]);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

long long arr [110000];



int main ()

{

int n,w;

int wi,vi;

cin >>n>>w;

int i,j;

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

{

cin >>wi>>vi;

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

{

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

}

}

long long t ;

t = 0;

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

{

t = max (t , arr [i]);

}

cout <<t<<'\n';



}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstdio>

#include<fstream>

#include<algorithm>

#include<cmath>

#include<deque>

#include<vector>

#include<queue>

#include<string>

#include<cstring>

#include<map>

#include<stack>

#include<set>

#define mem(a,b) memset(a,b,sizeof(a))

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

const int maxn =1000100;

typedef pair<ll,ll>p1;

typedef pair<pair<ll,ll>,ll>p2;

map<pair<pair<ll,ll>,ll>,ll>m1;

map<pair<ll,ll>,ll>m2;

const int MOD = 1e9;

const int N=351;

const int inf = 0x3f3f3f3f;

typedef pair<char, int> PAIR;

map<string,int>mm;

ll w[maxn],v[maxn],c[maxn];

ll dp[maxn];

int main()

{

    mem(dp,0);

    int n,k;

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

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

    {

        scanf("%lld%lld",&w[i],&v[i]);

    }

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

    {

        for(int j=k;j>=w[i];j--)

        {

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

        }

    }

    cout<<dp[k]<<endl;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

long long arr [110000];



int main ()

{

int n,w;

int wi,vi;

cin >>n>>w;

int i,j;

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

{

cin >>wi>>vi;

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

{

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

}

}

long long t ;

t = 0;

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

{

t = max (t , arr [i]);

}

cout <<t<<'\n';



}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

using namespace __gnu_pbds;



template <typename T>

using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;



typedef long long ll;

typedef pair<ll, ll> pll;

typedef pair<int, int> pii;

typedef complex<double> point;



const ll N = 105;

const ll INF = 1e9;

const int MOD = 1e9 + 7;

const double EPS = 1e-7;

const double PI = acos(-1.0);



ll dp[100005];

ll n, m, w[N], v[N], ans;



int main()

{

    ios::sync_with_stdio(false);

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

    cin >> n >> m;

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

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



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

        dp[i] = -1;



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

        for(int j = 100000; j >= 0; j--)

            if(w[i] <= j && dp[j - w[i]] != -1)

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

    

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

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

    

    cout << ans << endl;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;

typedef pair<ll, ll> pll;

typedef pair<int, int> pii;



#define endl "\n"



const ll INF = 1e15;

const int MOD = 1e9 + 7;

const double EPS = 1e-9;

const double PI = acos(-1.0);



mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());



const int N = 1e2 + 5;

const int M = 1e5 + 5;



ll n, W, w[N], v[N], dp[M];



int main() {

    ios::sync_with_stdio(false);

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



    cin >> n >> W;



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

        cin >> 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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



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

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

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

		for(int j = N-1; j-p[i] >= 0; j--){

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

		}

	}



	ll ans = 0;

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



	cout <<ans <<endl;

    	return 0;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <stdlib.h>

long long max(long long a,long long b)

{

	if(a>b)	return a;

	return b; 

}

int main()

{

	int i,n,j,W;

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

	long long *dp=(long long*)malloc(sizeof(long long)*W);

	dp[0]=0;

	for(i=1;i<=W;i++) dp[i]=-1;

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

	{

		int w1,v1;

		scanf("%d %d",&w1,&v1);

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

		{

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

			if(j+w1<=W) dp[j+w1] = max(dp[j+w1],dp[j]+v1);

		}	

	}

	long long ans=-1;

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

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

	printf("%lld",ans);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <algorithm>

#include <numeric>

#include <cmath>

#include <set>

#include <tuple>

#include <functional>

#include <map>

#include <unordered_map>

#include <queue>

#include <tuple>



using namespace std;



#define endl '\n'



using ull = unsigned long int;

using ll = long long;



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  const int precision = 13;

  cout.precision(precision);

  cout.setf(ios_base::fixed);



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

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



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

    ll w, v; cin >>  w >> v;

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

      if (j-w == 0 or dp[j-w]) {

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

      }

    }

  }



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



  return 0;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <stdlib.h>

long long max(long long a,long long b)

{

	if(a>b)	return a;

	return b; 

}

int main()

{

	int i,n,j,W;

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

	long long *dp=(long long*)malloc(sizeof(long long)*W);

	dp[0]=0;

	for(i=1;i<=W;i++) dp[i]=-1;

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

	{

		int w1,v1;

		scanf("%d %d",&w1,&v1);

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

		{

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

			if(j+w1<=W) dp[j+w1] = max(dp[j+w1],dp[j]+v1);

		}	

	}

	long long ans=-1;

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

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

	printf("%lld",ans);

}

// Fastest known solution for this problem: