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

}

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



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

}

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



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

}


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

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

}


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

#include<iostream>

#include<algorithm>

#include<queue>

#define inf 0x3f3f3f3f

using namespace std;

typedef long long LL;

const int maxn = 1e5+5;



LL w[maxn],v[maxn],dp[maxn];



int main(){

	int n,m;

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

	for(int i = 1; i <= n; i++) scanf("%lld %lld", &w[i],&v[i]);

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

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

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

		}

	}

	printf("%lld",dp[m]);

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

}


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

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;



const int MAXN = 1e5 + 100;

const int inf = 0x3f3f3f3f;

int n, k;

long long dp[105][MAXN];//dp[i][j]：前i个物品，容量为j时的最大价值

int w[MAXN];

long long v[MAXN];



int main(){

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

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

		int a, b;

		scanf("%d %d", &a, &b);

		w[i] = a, v[i] = b;

	}

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

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

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

			else dp[i][j] = dp[i-1][j] > dp[i-1][j-w[i]]+v[i] ? dp[i-1][j] : dp[i-1][j-w[i]]+v[i];

		}

	}

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

	return 0;

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

}


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

#include <algorithm>



using namespace std;



int main () {

	int n, w;

	cin >> n >> w;

	int peso[n];

	long int valor[n];

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

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



	long int solucoes[n+1][w+1];

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

		solucoes[0][i] = 0;

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

		int curPeso = peso[i-1];

		long int curValor = valor[i-1];



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

			if (j - curPeso >= 0)

				solucoes[i][j] = max(solucoes[i - 1][j],(curValor + solucoes[i - 1][j - curPeso]));

			else

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

		}

	}



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

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

}


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

#include <algorithm>

#include <bits/stdc++.h>



using namespace std;



int main(){

    int N, W;

    cin >> N >> W;

    long int items[N+1][2];

    items[0][0] = 0;

    items[0][1] = 0;

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

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

    }

    long int mat[W+1][N+1];

    mat[0][0] = 0;

    for(int num_item = 0; num_item <= N; num_item++){

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

            if(num_item == 0 || capacidade == 0){

                mat[capacidade][num_item] = 0;

            }

            else {

                long int custo_anterior = mat[capacidade][max(num_item-1, 0)];

                long int peso_item_atual = items[num_item][0];

                long int valor_item_atual = items[num_item][1];

                long int capacidade_restante = capacidade - peso_item_atual;

                long int custo_com_item_atual = valor_item_atual + mat[capacidade_restante][num_item-1];

                if(capacidade_restante < 0){

                    mat[capacidade][num_item] = custo_anterior;

                }

                else {

                    mat[capacidade][num_item] = max(custo_anterior, custo_com_item_atual);

                }

            }

        }

    }

    cout << mat[W][N];

    return 0;

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

}


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

using namespace std;



unsigned long long achaValorMaximo(unsigned long long valorDosItens[], int pesoDosItens[], int capacidade, int qtdItens)

{

    unsigned long long tabelaDeMaximos[qtdItens + 1][capacidade + 1];



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

    {

        tabelaDeMaximos[0][i] = 0;

    }

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

    {

        tabelaDeMaximos[i][0] = 0;

    }



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

    {

        for (int iCapacidade = 1; iCapacidade <= capacidade; iCapacidade++)

        {

            if (pesoDosItens[i - 1] <= iCapacidade)

            {

                if ((valorDosItens[i - 1] + tabelaDeMaximos[i - 1][iCapacidade - pesoDosItens[i - 1]]) > tabelaDeMaximos[i - 1][iCapacidade])

                {

                    tabelaDeMaximos[i][iCapacidade] = valorDosItens[i - 1] + tabelaDeMaximos[i - 1][iCapacidade - pesoDosItens[i - 1]];

                }

                else

                {

                    tabelaDeMaximos[i][iCapacidade] = tabelaDeMaximos[i - 1][iCapacidade];

                }

            }

            else

            {

                tabelaDeMaximos[i][iCapacidade] = tabelaDeMaximos[i - 1][iCapacidade];

            }

        }

    }

    return tabelaDeMaximos[qtdItens][capacidade];

}



int main()

{



    int qtdItens, capacidade;

    cin >> qtdItens >> capacidade;

    int pesoDosItens[qtdItens];

    unsigned long long valorDosItens[qtdItens];

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

    {

        cin >> pesoDosItens[i] >> valorDosItens[i];

    }



    unsigned long long valorMaximo = achaValorMaximo(valorDosItens, pesoDosItens, capacidade, qtdItens);

    cout << valorMaximo << endl;

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

}


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

#define ll long long

using namespace std;



ll arr[107], weight[107];

ll dp[107][100007];

bool vis[107][100007];

ll W;

int n;



ll rec( int i, ll w )

{

    if(i>=n)

        return 0;

    if(vis[i][w])

        return dp[i][w];



    ll q1= rec( i+1, w );

    ll q2= 0;



    if( weight[i]+w<= W )

        q2= arr[i]+rec( i+1, w+weight[i] );



    vis[i][w]= 1;



    return dp[i][w]= max(q1,q2);

}



int main()

{

    cin>>n>>W;



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

        cin>>weight[i]>>arr[i];



    cout<< rec( 0, 0 ) <<endl;

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

}


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

#include <bits/stdc++.h>

#include <math.h>

#include <string>

#include <stdio.h>



int R; // n. requisitos

int TMP; // tempo total

long long int solMelhor;



int T[101]; //tempo para execução do requisito

long long int V[101]; //valor adquirido





long long int memo[101][100001];



long long int max(long a, long b){

  if(a>b)

    return a;

  else

    return b;

}



void inicializar(){



  std::cin >> R >> TMP;



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

    std::cin >> T[i] >> V[i];

  }

  for(int i=0; i<R+1; i++)

    for(long long int j=0; j<TMP+1;j++)

      memo[i][j]=0;

}



void imprimeResultados(){

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

    for(long long int j = 0;j<=TMP;j++){

      std::cout<<memo[i][j]<<"|";

    }

    std::cout<<std::endl;

  }

  std::cout << solMelhor;    

}



long long int v1,v2;

long long int nrp(){

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

    for(long long int j = 1;j<=TMP;j++){

      //v1 = memo[i][j-1];

      if(T[i]>j)

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

      else{

        v1=memo[i-1][j-T[i]]+V[i];

        v2=memo[i-1][j];

        memo[i][j] = max(v1,v2);

      }

    }

  }

  return memo[R][TMP];

}



int main() {

  inicializar();

  

  solMelhor = nrp();



 std::cout << solMelhor;  

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

}


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

/**

*   author: j o s e m a g o

*   date:

**/

using namespace std;

#pragma GCC optimize ("Ofast")

#define f first

#define s second

#define mp make_pair

#define lb lower_bound

#define ub upper_bound

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

#define mset(a,v) memset(a,v,sizeof(a))

#define pb push_back

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

#define rsz resize

#define ln "\n"



typedef double db;

typedef unsigned long long ull;

typedef long long ll;

typedef long double ld;

const ld PI = 2*acos(0.0);

const int MOD = 1000000007;









ll table[100009];





int main(){



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

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



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





    int n,m;

    cin >> n >> m;

    vector<pair<int,ll> >v(n);





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

        cin >> v[i].f >> v[i].s;

    }



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

        for(int cap = m;cap >= v[i].f;cap--){

            table[cap] = max(table[cap],table[cap-v[i].f]+v[i].s);

        }

    }



    cout<<table[m];







    return 0;

}

/*

5 5

1 1000000000

1 1000000000

1 1000000000

1 1000000000

1 1000000000







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

}


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

#include<cmath>

#include<algorithm>

using namespace std;



long long K[101][100001];

int values[101];

int weights[101];



long long knapSack(int W, int wt[], int val[], int n)

{

	int i, w;





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

	{

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

		{

			if (i == 0 || w == 0)

				K[i][w] = 0;

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

				K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);

			else

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

		}

	}



	return K[n][W];

}





int main()

{

	int n, w;

	cin >> n >> w;

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

	{

		cin >> weights[i] >> values[i];

	}



	cout << knapSack(w, weights, values, n) << endl;

	system("pause");

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

}


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

#define eps 1e-3

#define pi acos(-1.0)

#define inf 0x3f3f3f3f

#define debug1 cout<<"&&";

#define debug2 cout<<"**";

#define pb push_back

#define ms(a, x) memset(a, x, sizeof(a))

#define forn(i, n) for(int i = 0; i < n; ++i)

#define for1(i, n) for(int i = 1; i <= n; ++i) 

typedef double db;

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

const int mod = 1e9;

const int N = 1e5+10;

/*=======================================================================*/



ll n, W, w[N], v[N], f[N];

int main() {

  cin >> n >> W;

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



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

     for (int l = W; l >= w[i]; l--) {

      //   debug1

      //   cout << i << endl;

      //   cout << f[l - w[i]] + v[i] << " " << f[l] << endl;

        if (f[l - w[i]] + v[i] > f[l]) {

            f[l] = f[l - w[i]] + v[i];

            // debug1

            // cout << i << " " << l << endl;

         }

     }

   //   cout << i << " " << n << endl;

  }

    

      

  cout << f[W] << endl;

  return 0;

}