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

}


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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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

}


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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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

}

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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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







*/

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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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

}


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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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

}

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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const int N=105;

const int maxn=1e5+5;

int a[N],v[N];

ll dp[N][maxn];

int main(){

	int n,k;

	cin>>n>>k;

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

		cin>>a[i]>>v[i];

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

		dp[i][0]=0,	dp[0][i]=0;

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

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

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

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

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

	return 0;

} 

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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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

using namespace std;

int w[105], val[105];

long long dp[100005];

int main()

{

    int t,m,res=-1;    

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

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

    {

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

    }

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

    {

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

        {

            if(j>=w[i])

            {

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

            }

        }

    }    

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

    return 0;

}


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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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

using namespace std;



typedef long long ll;

typedef pair<int, int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;

typedef vector<ll> vll;



ll dp(int mw, int n, int w[], int v[]){

	long memo[n+1][mw+1];

	int i , j;

//	memset(memo, 0, sizeof memo);

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

		for(j = 0; j <= mw; j++){

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

				memo[i][j] = 0;

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

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

			else

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

//			cout << memo[i][j] << ' ';

		}

//		cout << endl;

	}

//	cout << i << ' ' << j << endl;

	return memo[n][mw];

}



int main() {

	int n, mw;

	cin >> n >> mw;

	int w[n],v[n];

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

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

	}

	cout << dp(mw,n,w,v);

	return 0;

}


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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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

#define MAXN 110

#define MAXW 100010

#define ll long long



using namespace std;



ll n, W, ans, w[MAXN], v[MAXN], dp[MAXW];

bool mk[MAXW];



void init(){

    mk[0]=true;

}



int main(){



    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);



    cin>>n>>W;



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

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

    }



    init();



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

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

            if(mk[j]&&dp[j]+v[i]>dp[j+w[i]]){

                mk[j+w[i]]=true;

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

            }

        }

    }



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



    cout<<ans;



return 0;

}


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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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



using namespace std;



//Recursive Definition

long long maximumCost(long long * weights, long long * values, long long N, long long W){

if(N == 1){

  if(weights[N-1] <= W){

   return  values[N-1];

  }else{

   return 0;

  }

}else if(N > 1){

  if(weights[N-1] <= W){

   return  max(values[N-1] + maximumCost(weights,values,N-1,W-weights[N-1]),maximumCost(weights,values,N-1,W));

  }else{

   return maximumCost(weights,values,N-1,W);

  }

}

}

//Now Using Memoization

//Bottom up algorithm Reference: https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

long long knapSack(long long W, long long * weights, long long * values, long long N) {

   long long i, w;

   long long WN[N+1][W+1];

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

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

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

           WN[i][w] = 0;

           }else if (weights[i-1] <= w){

           WN[i][w] = max(values[i-1] + WN[i-1][w-weights[i-1]],WN[i-1][w]);

           }else{

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

           }

       }

   }

   return WN[N][W];

}



int main(){

    long long N;

    cin>>N;

    long long W;

    cin>>W;

    long long * weights = new long long[N];

    long long * values = new long long[N];

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

     cin>>weights[i];

     cin>>values[i];

    }

  //  cout<<maximumCost(weights,values,N,W)<<endl;

    cout<<knapSack(W,weights,values,N)<<endl;

    delete[] weights;

    delete[] values;

    return 0;

}

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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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

#include<algorithm>



using namespace std;



const int maxn = 100000+5;

const int inf = 0x3f3f3f3f;

const int maxm=100000+5;



long long a[maxn],t[maxn],f[maxm];



int main(){

	int n,m;

	cin>>n>>m;

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

    	cin>>t[i]>>a[i];

    }

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

    	f[j]=-inf;

    }

    f[0]=0;

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

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

    		if(j>=t[i]){

    			f[j]=max(f[j],f[j-t[i]]+a[i]);

    		}	

    		}

    }

    long long ret=-1;

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

    	ret=max(ret,f[j]);

    }

cout<<ret <<endl;

return 0;

	

}

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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

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

using namespace std;

 

int main() {

  int N,W;

 

  cin >> N >> W;

 

  vector<int> w(N), v(N);

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

 

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

    cin >> w[i];

    cin >> v[i];

  }

 

 

 

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

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

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

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

      }

      else {

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

      }

    }

  }

 

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

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

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

  //   }

  //   cout << endl;

  // }

 

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

 

  return 0;

}

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


#include<stdio.h> 



long long max(long long a, long long b) { return (a > b)? a : b; } 



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

{  

      

long long i, w; 

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

  

   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() 

{ 

	

	long long n,W;

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

	long long val[n] ; 

	long long wt[n]; 

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

		scanf("%lld %lld",&wt[i],&val[i]);

	}

	printf("%lld", knapSack(W, wt, val, n)); 

	return 0; 

}