stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.547986366490268x):
#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,T,cas=0;

	cin>>n>>W;

	vector<ll> dp(W+1);

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

		int weight, val;

		cin>>weight>>val;

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

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

		}

	}

	cout<<dp[W]<<endl;

	return 0;

}
// Slower C++ solution:
#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;

}

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

}
// Slower C++ solution:
//

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

}

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

}
// Slower C++ solution:
#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;

}

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

}
// Slower C++ solution:
#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;

}


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

}
// Slower C++ solution:
#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;

}




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

}
// Slower C++ solution:
#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;

}


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

}
// Slower C++ solution:
#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;

}

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

}
// Slower C++ solution:
#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;

}

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

}
// Slower C++ solution:
#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";

}

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

}
// 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,T,cas=0;

	cin>>n>>W;

	vector<ll> dp(W+1);

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

		int weight, val;

		cin>>weight>>val;

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

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

		}

	}

	cout<<dp[W]<<endl;

	return 0;

}

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

}
// Slower C++ solution:
#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;

}

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

using namespace std;



int main() {



	int n, capac;

	scanf("%d", &n);

	scanf("%d", &capac);

	

	unsigned long peso[n];

	unsigned long valor[n];

	unsigned long mPesVal[capac+1];

	

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

		//scanf("%lu", (peso+i));

		//scanf("%lu", (valor+i));

		

		cin >> *(peso + i) >> *(valor + i);

	}

	

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

		*(mPesVal + i)=0;

	}

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

		for(int j = capac;j >= peso[i];j--){

		  *(mPesVal + j) = max(*(mPesVal + j), (*(mPesVal + (j - *(peso + i))) + *(valor + i)));

		  //printf("*(dp + %d) = %x\n", j, *(dp + j));

		}

	}

	

	cout << *(mPesVal + capac) << endl;

	//return 0;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.6024780584213123x):
/***************************************************************

Esse é um problema parecido com o problema da mochila.

Usando o código do exercício anterior

Taro realmente precisa procurar o que fazer

n = qtd de itens

w = limite da mochila

mochila[peso][valor] de cada item

***************************************************************/

#include <bits/stdc++.h>



using namespace std;



int main(){

    int n=0, w=0;



    cin >> n >> w;

    

    int peso[n+1], valor[n+1];

    //Sem ser ull res = 705032704, valor nada a ver

    //ATENÇÃO: The answer may not fit into a 32-bit integer type.

    unsigned long long resp[n+1][w+1], q=0;

    

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

        cin >> peso[i] >> valor[i];

    }



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

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

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

                q = 0;

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

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

            } else{

                 q = resp[i-1][j]; 

            }

            // cout << "j: " << j << " j: " << j << endl;

            resp[i][j]=q;

            // cout << "To no j" << endl;

        }

        // cout << "To no i" << endl;

    }

    

    

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

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

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

    //     }

    //     cout << endl;

    // }

    

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

}
// Slower C++ solution:
#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;

}

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



using namespace std;



#define ff first

#define ss second

#define int long long

#define pii pair<int,int>



signed main(){

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	int n,i,j,m;

	cin>>m>>n;

	int memo[n+1];

	for(i=1;i<n+1;i++)memo[i]=-1;

	memo[0]=0;

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

		pii novo;

		cin>>novo.ff>>novo.ss;

		for(j=n-novo.ff;j>=0;j--){

			if(memo[j]!=-1){

				memo[j+novo.ff] = max(memo[j+novo.ff],memo[j]+novo.ss);

			}

		}

	}

	int maior=-1;

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

		if(memo[i]>maior)maior=memo[i];

	}	



	cout<<maior<<endl;

}