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

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, ww;

  cin >> n >> ww;

  vll w(n), v(n);

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

  vll dp(100001, 0);

  vector<vll> check(1, vll(n, 0));

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

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

    ll memo = -1;

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

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      vll x = check[i - w[memo]];

      x[memo] = 1;

      check.push_back(x);

    }

    else check.push_back(check[i - 1]);

  }

  cout << dp[ww] << endl;

}

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

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

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

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

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



  vector<vll> dp(n, vll(w + 1));

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

    if (i < ww[0]) dp[0][i] = 0;

    else dp[0][i] = v[0];

  }

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

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

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

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

    }

  }

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

}

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

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, ww;

  cin >> n >> ww;

  vll w(n), v(n);

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

  vll dp(100001, 0);

  vector<vll> check(1, vll(n, 0));

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

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

    ll memo = -1;

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

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      check.emplace_back(check[i - w[memo]]);

      check[i][memo] = 1;

    }

    else check.emplace_back(check[i - 1]);

  }

  cout << dp[ww] << endl;

}

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

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

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

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

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



  vector<vll> dp(n, vll(w + 1));

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

    if (i < ww[0]) dp[0][i] = 0;

    else dp[0][i] = v[0];

  }

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

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

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

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

    }

  }

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

}

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

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, lim;

  cin >> n >> lim;

  vll w(n), v(n);

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

  vll dp(100001, 0);

  vector<vll> check(1, vll(n, 0));

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

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

    ll memo = -1;

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

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      vll x = check[i - w[memo]];

      x[memo] = 1;

      check.push_back(x);

    }

    else check.push_back(check[i - 1]);

  }

  cout << dp[lim] << endl;

}

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

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

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

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

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



  vector<vll> dp(n, vll(w + 1));

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

    if (i < ww[0]) dp[0][i] = 0;

    else dp[0][i] = v[0];

  }

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

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

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

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

    }

  }

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

}

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

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

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

		for (ULL j = w; j >= W[i]; j--)

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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



using namespace std;

#define MAX(a,b) (a>b?a:b)

int main(){

  int num, cap;

  scanf("%d %d", &num,&cap);

  int itens[num+1][2];

  for (size_t i = 1; i < num+1; i++) {

      scanf("%d %d",itens[i],itens[i]+1);

    // printf("%d %d\n",itens[i][0],itens[i][1]);

  }

  num++,cap++;

  long long parciais[num][cap];

  for (size_t i = 0; i < cap; i++) {

    parciais[0][i] = 0;

  }

  for (size_t i = 1; i < num; i++) {

    for (size_t j = 0; j < cap; j++) {

      if(j < itens[i][0])

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

      else

        parciais[i][j] = MAX(parciais[i-1][j],(long long)itens[i][1] + parciais[i-1][j-itens[i][0]]);

    }

  }

  // printf("   ");

  // for (size_t i = 0; i < num; i++) {

  //   printf("qtd%d            ", i);

  // }

  // printf("\n");

  // printf("\n");

  // for (size_t i = 0; i < cap; i++) {

  //   printf("%d  ", i);

  //   for (size_t j = 0; j < num; j++) {

  //     printf("%02lld              ", parciais[j][i]);

  //   }

  //   printf("\n\n");

  // }



  num--,cap--;

  printf("%lld\n",parciais[num][cap]);

}


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

#include <cmath>

#include <cstring>

using namespace std;

long long n,m;

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

long long dp[101][100001];



int main(){

	cin>>n>>m;

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

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

	}

//	memset(dp,-1,sizeof(dp));

	for (int i=n-1;i>=0;i--){

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

			if (j<w[i]){

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

			}else {

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

			}

		}

	}

	cout<<dp[0][m]<<endl;

	return 0;

}

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



using namespace std;

#define MAX(a,b) (a>b?a:b)

int main(){

  int num, cap;

  scanf("%d %d", &num,&cap);

  int itens[num+1][2];

  for (size_t i = 1; i < num+1; i++) {

      scanf("%d %d",itens[i],itens[i]+1);

    // printf("%d %d\n",itens[i][0],itens[i][1]);

  }

  num++,cap++;

  long long parciais[num][cap];

  for (size_t i = 0; i < cap; i++) {

    parciais[0][i] = 0;

  }

  for (size_t i = 1; i < num; i++) {

    for (size_t j = 0; j < cap; j++) {

      if(j < itens[i][0])

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

      else

        parciais[i][j] = MAX(parciais[i-1][j],(long long)itens[i][1] + parciais[i-1][j-itens[i][0]]);

    }

  }

  // printf("   ");

  // for (size_t i = 0; i < num; i++) {

  //   printf("qtd%d            ", i);

  // }

  // printf("\n");

  // printf("\n");

  // for (size_t i = 0; i < cap; i++) {

  //   printf("%d  ", i);

  //   for (size_t j = 0; j < num; j++) {

  //     printf("%02lld              ", parciais[j][i]);

  //   }

  //   printf("\n\n");

  // }



  num--,cap--;

  printf("%lld\n",parciais[num][cap]);

}


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

#include <iostream>

#include <cstdio>

#include <algorithm>



using namespace std;



typedef long long ll;



const int maxn = 1e5 + 10;



ll max(ll x, ll y)

{

	return x < y ? y : x;

}



ll n, m, w[maxn], v[maxn], f[maxn];



int main()

{

    cin >> n >> m;

    

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

    {

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

    }

    

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

    {

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

        {

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

        }

    }

    cout << f[m] << endl;

    

    return 0;

}

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



using namespace std;

#define MAX(a,b) (a>b?a:b)

int main(){

  int num, cap;

  scanf("%d %d", &num,&cap);

  int itens[num+1][2];

  for (size_t i = 1; i < num+1; i++) {

      scanf("%d %d",itens[i],itens[i]+1);

    // printf("%d %d\n",itens[i][0],itens[i][1]);

  }

  num++,cap++;

  long long parciais[num][cap];

  for (size_t i = 0; i < cap; i++) {

    parciais[0][i] = 0;

  }

  for (size_t i = 1; i < num; i++) {

    for (size_t j = 0; j < cap; j++) {

      if(j < itens[i][0])

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

      else

        parciais[i][j] = MAX(parciais[i-1][j],(long long)itens[i][1] + parciais[i-1][j-itens[i][0]]);

    }

  }

  // printf("   ");

  // for (size_t i = 0; i < num; i++) {

  //   printf("qtd%d            ", i);

  // }

  // printf("\n");

  // printf("\n");

  // for (size_t i = 0; i < cap; i++) {

  //   printf("%d  ", i);

  //   for (size_t j = 0; j < num; j++) {

  //     printf("%02lld              ", parciais[j][i]);

  //   }

  //   printf("\n\n");

  // }



  num--,cap--;

  printf("%lld\n",parciais[num][cap]);

}


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



using namespace std;





int main()

{

	int n, W;

	cin >> n >> W;



	vector<long long> w(n + 1), v(n + 1);

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



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

		}

	}



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

}

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



using namespace std;

#define MAX(a,b) (a>b?a:b)

int main(){

  int num, cap;

  scanf("%d %d", &num,&cap);

  int itens[num+1][2];

  for (size_t i = 1; i < num+1; i++) {

      scanf("%d %d",itens[i],itens[i]+1);

    // printf("%d %d\n",itens[i][0],itens[i][1]);

  }

  num++,cap++;

  long long parciais[num][cap];

  for (size_t i = 0; i < cap; i++) {

    parciais[0][i] = 0;

  }

  for (size_t i = 1; i < num; i++) {

    for (size_t j = 0; j < cap; j++) {

      if(j < itens[i][0])

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

      else

        parciais[i][j] = MAX(parciais[i-1][j],(long long)itens[i][1] + parciais[i-1][j-itens[i][0]]);

    }

  }

  // printf("   ");

  // for (size_t i = 0; i < num; i++) {

  //   printf("qtd%d            ", i);

  // }

  // printf("\n");

  // printf("\n");

  // for (size_t i = 0; i < cap; i++) {

  //   printf("%d  ", i);

  //   for (size_t j = 0; j < num; j++) {

  //     printf("%02lld              ", parciais[j][i]);

  //   }

  //   printf("\n\n");

  // }



  num--,cap--;

  printf("%lld\n",parciais[num][cap]);

}


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

using ll = long long;

using namespace std;



int n, w;

ll dp[102][100100];

ll val[110], wt[110];



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 = 0; weight <= w; ++weight) {

            if ( weight == 0 ) {

                dp[pos][weight] = 0;

                continue;

            }

            dp[pos][weight] = dp[pos - 1][weight];

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

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

        }

    }





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

    return 0;

}


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



using namespace std;

#define MAX(a,b) (a>b?a:b)

int main(){

  int num, cap;

  scanf("%d %d", &num,&cap);

  int itens[num+1][2];

  for (size_t i = 1; i < num+1; i++) {

      scanf("%d %d",itens[i],itens[i]+1);

    // printf("%d %d\n",itens[i][0],itens[i][1]);

  }

  num++,cap++;

  long long parciais[num][cap];

  for (size_t i = 0; i < cap; i++) {

    parciais[0][i] = 0;

  }

  for (size_t i = 1; i < num; i++) {

    for (size_t j = 0; j < cap; j++) {

      if(j < itens[i][0])

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

      else

        parciais[i][j] = MAX(parciais[i-1][j],(long long)itens[i][1] + parciais[i-1][j-itens[i][0]]);

    }

  }

  // printf("   ");

  // for (size_t i = 0; i < num; i++) {

  //   printf("qtd%d            ", i);

  // }

  // printf("\n");

  // printf("\n");

  // for (size_t i = 0; i < cap; i++) {

  //   printf("%d  ", i);

  //   for (size_t j = 0; j < num; j++) {

  //     printf("%02lld              ", parciais[j][i]);

  //   }

  //   printf("\n\n");

  // }



  num--,cap--;

  printf("%lld\n",parciais[num][cap]);

}


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

using namespace std;

#define   ll  long long

ll dp[105][100005];

int main()

{

    ll i,j,n,w,wt[105],val[105];

    cin>>n>>w;

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

    {

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

    }

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

    {

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

        {

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

            {

                dp[i][j]=0;

            }

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

            {

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

            }

            else

            {

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

            }

        }

    }

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

    return 0;

}




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



using namespace std;

#define MAX(a,b) (a>b?a:b)

int main(){

  int num, cap;

  scanf("%d %d", &num,&cap);

  int itens[num+1][2];

  for (size_t i = 1; i < num+1; i++) {

      scanf("%d %d",itens[i],itens[i]+1);

    // printf("%d %d\n",itens[i][0],itens[i][1]);

  }

  num++,cap++;

  long long parciais[num][cap];

  for (size_t i = 0; i < cap; i++) {

    parciais[0][i] = 0;

  }

  for (size_t i = 1; i < num; i++) {

    for (size_t j = 0; j < cap; j++) {

      if(j < itens[i][0])

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

      else

        parciais[i][j] = MAX(parciais[i-1][j],(long long)itens[i][1] + parciais[i-1][j-itens[i][0]]);

    }

  }

  // printf("   ");

  // for (size_t i = 0; i < num; i++) {

  //   printf("qtd%d            ", i);

  // }

  // printf("\n");

  // printf("\n");

  // for (size_t i = 0; i < cap; i++) {

  //   printf("%d  ", i);

  //   for (size_t j = 0; j < num; j++) {

  //     printf("%02lld              ", parciais[j][i]);

  //   }

  //   printf("\n\n");

  // }



  num--,cap--;

  printf("%lld\n",parciais[num][cap]);

}


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

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 100000 + 100

#define ll long long int

ll N[MAXN];

ll w[200];

ll v[200];

ll n;

ll max_V;

int main()

{

    cin>>n>>max_V;

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

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

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

        for(int j = max_V;j >= v[i];--j)

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

    cout<<N[max_V]<<endl;



    return 0;

}


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



using namespace std;

#define MAX(a,b) (a>b?a:b)

int main(){

  int num, cap;

  scanf("%d %d", &num,&cap);

  int itens[num+1][2];

  for (size_t i = 1; i < num+1; i++) {

      scanf("%d %d",itens[i],itens[i]+1);

    // printf("%d %d\n",itens[i][0],itens[i][1]);

  }

  num++,cap++;

  long long parciais[num][cap];

  for (size_t i = 0; i < cap; i++) {

    parciais[0][i] = 0;

  }

  for (size_t i = 1; i < num; i++) {

    for (size_t j = 0; j < cap; j++) {

      if(j < itens[i][0])

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

      else

        parciais[i][j] = MAX(parciais[i-1][j],(long long)itens[i][1] + parciais[i-1][j-itens[i][0]]);

    }

  }

  // printf("   ");

  // for (size_t i = 0; i < num; i++) {

  //   printf("qtd%d            ", i);

  // }

  // printf("\n");

  // printf("\n");

  // for (size_t i = 0; i < cap; i++) {

  //   printf("%d  ", i);

  //   for (size_t j = 0; j < num; j++) {

  //     printf("%02lld              ", parciais[j][i]);

  //   }

  //   printf("\n\n");

  // }



  num--,cap--;

  printf("%lld\n",parciais[num][cap]);

}


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

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <sstream>

#include <queue>

#include <deque>

#include <bitset>

#include <iterator>

#include <list>

#include <stack>

#include <map>

#include <set>

#include <functional>

#include <numeric>

#include <utility>



using namespace std;

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	int n, mw;

	cin >> n >> mw;

	vector<long long> memo;

	memo.resize(mw + 1, 0);

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

		int w, v;

		cin >> w >> v;

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

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

		}

	}

	cout << memo.back();

	return 0;

}

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



using namespace std;

#define MAX(a,b) (a>b?a:b)

int main(){

  int num, cap;

  scanf("%d %d", &num,&cap);

  int itens[num+1][2];

  for (size_t i = 1; i < num+1; i++) {

      scanf("%d %d",itens[i],itens[i]+1);

    // printf("%d %d\n",itens[i][0],itens[i][1]);

  }

  num++,cap++;

  long long parciais[num][cap];

  for (size_t i = 0; i < cap; i++) {

    parciais[0][i] = 0;

  }

  for (size_t i = 1; i < num; i++) {

    for (size_t j = 0; j < cap; j++) {

      if(j < itens[i][0])

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

      else

        parciais[i][j] = MAX(parciais[i-1][j],(long long)itens[i][1] + parciais[i-1][j-itens[i][0]]);

    }

  }

  // printf("   ");

  // for (size_t i = 0; i < num; i++) {

  //   printf("qtd%d            ", i);

  // }

  // printf("\n");

  // printf("\n");

  // for (size_t i = 0; i < cap; i++) {

  //   printf("%d  ", i);

  //   for (size_t j = 0; j < num; j++) {

  //     printf("%02lld              ", parciais[j][i]);

  //   }

  //   printf("\n\n");

  // }



  num--,cap--;

  printf("%lld\n",parciais[num][cap]);

}


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

using namespace std;

#define int long long int



int n;

int w;

vector< vector<int> > items;

vector< vector<int> > dp;



int knapp(int item, int weight){

	if(item == n || dp[item][weight] == -1){

		if(item == n){

			return 0;

		}

		else{

			if(weight - items[item][0] >= 0){

				dp[item][weight] = max(dp[item][weight], items[item][1] + knapp(item+1, weight - items[item][0]));

			}

			dp[item][weight] = max(dp[item][weight], knapp(item+1, weight));

			return dp[item][weight];

		}

	}

	else{

		return dp[item][weight];

	}

}



main(){

	cin >> n >> w;

	

	items.resize(n, vector<int>(2));

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



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

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

	}



	cout << knapp(0, w) << "\n";

}

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



using namespace std;

#define MAX(a,b) (a>b?a:b)

int main(){

  int num, cap;

  scanf("%d %d", &num,&cap);

  int itens[num+1][2];

  for (size_t i = 1; i < num+1; i++) {

      scanf("%d %d",itens[i],itens[i]+1);

    // printf("%d %d\n",itens[i][0],itens[i][1]);

  }

  num++,cap++;

  long long parciais[num][cap];

  for (size_t i = 0; i < cap; i++) {

    parciais[0][i] = 0;

  }

  for (size_t i = 1; i < num; i++) {

    for (size_t j = 0; j < cap; j++) {

      if(j < itens[i][0])

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

      else

        parciais[i][j] = MAX(parciais[i-1][j],(long long)itens[i][1] + parciais[i-1][j-itens[i][0]]);

    }

  }

  // printf("   ");

  // for (size_t i = 0; i < num; i++) {

  //   printf("qtd%d            ", i);

  // }

  // printf("\n");

  // printf("\n");

  // for (size_t i = 0; i < cap; i++) {

  //   printf("%d  ", i);

  //   for (size_t j = 0; j < num; j++) {

  //     printf("%02lld              ", parciais[j][i]);

  //   }

  //   printf("\n\n");

  // }



  num--,cap--;

  printf("%lld\n",parciais[num][cap]);

}


// Fastest known solution for this problem: