stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

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

//cout<<fixed<<setprecision(6)<<n<<endl;

// transform(s.begin(), s.end(), s.begin(), ::tolower);

//double PI=3.14159265359,c=0;

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

#define endl '\n'

#define ll long long

//#define f(n) for(int i=;i<n;i++)

double PI = acos(-1);

using namespace std;

void fast()

{

    std::ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

}

ll n,arr[1000][3],vist[111][100005];

ll Knapsack(int i,ll r)

{

    if(i>=n)

     return 0;

    if(vist[i][r])

     return vist[i][r];

    ll c1=Knapsack(i+1,r);

    ll c2=0;

    if(r>=arr[i][0])

    {

       c2=Knapsack(i+1,r-arr[i][0])+arr[i][1];

    }

    return vist[i][r]=max(c1,c2);

}

int main()

{

    fast();

    ll w;

    cin>>n>>w;

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

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

    

    cout<<Knapsack(0,w) <<endl;



    return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.805958902942293x):
/* be name Khoda */

#include <bits/stdc++.h>

using namespace std;



const int N = 100 * 1001, M = 105;

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



int main() {

	cin >> n >> W;

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

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

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

		for (int j = n - 1; 0 <= j; j--) {

			if (w[j] <= i)

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

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

		}

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

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

#define endl '\n'

#define fast_in ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define mp  make_pair

#define pb  push_back

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

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

#define  bit(x)  __builtin_popcountll(x)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

typedef pair <int,int> pii;

const int inf = (int) 1e9+99999, mod = (int)1e9+7;

const ll linf = (ll) 2e18+99999;

int mul (int x, int y) { return ((ll)x * y) % mod; } 

int sub (int x, int y) { x -= y; if (x < 0) return x + mod; return x; } 

int add (int x, int y) { x += y; if (x >= mod) return x - mod; return x; }

 

const int maxn = (int) 100001;

 

ll d[101][maxn];

ll w[101], c[101];



void solve () {

	int n, s;

	cin >> n >> s;

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

		cin >> w[i] >> c[i]; 

	}



	d[0][0] = 0;

	if (w[0] < maxn)

		d[0][w[0]] = c[0];



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

		if (w[i] < maxn)

			d[i][w[i]] = c[i];

		

		for (int k = s; k >= 0; k --) {

			d[i][k] = d[i-1][k];

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

				d[i][k] = max (d[i][k], d[i-1][k-w[i]] + c[i]);

			}

		}

	}



	ll res = 0;

	for (int k = s; k >= 0; k --) {

		res = max (res, d[n-1][k]);

	}



	cout << res;



}



main () { fast_in;

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

    int t = 1; //cin >> t;

    while (t --) {

    	solve ();    

    }

	return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

typedef long long ll;

using namespace std;

const int N=200010;

int main(){

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

	long long i,j,n,best=0,w[N],cap,a,b;

	cin>>n>>cap;

	memset(w,0,cap+1);

	while(n--){

		cin>>a>>b;

		for(i=cap;i>=a;--i) w[i]=max(w[i],w[i-a]+b);

	}

	for(i=1;i<=cap;++i){

		//cout<<w[i]<<" ";

		best=max(best,w[i]);

	}

	cout<<best;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.7736487394930314x):
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

#define rep(i,a,n) for (int i=a;i<n;i++)

#define per(i,a,n) for (int i=n-1;i>=a;i--)

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

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

#define clr(v, d) memset(v, d, sizeof(v))

#define fi first

#define se second

#define pp push_back

#define pb pop_back

#define pi 3.141592654

#define MOD 1000000007 

#define cons1 1e12

#define cons2 1e6

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int, ll> pa;

typedef unsigned long long int ull;

typedef double long dl;

const int N = 1e5+9,oo=-1e9;

ll dp[100][N], n, v[100][100];

ll sol(int i, int k){

	if (i == n)  return 0;

	if (!dp[i][k]) {

		if (k >= v[i][0])   

			dp[i][k] = v[i][1] + sol(i + 1, k - v[i][0]);

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

	}



	return dp[i][k];

}

void solve() {

	int w;

	cin >> n >> w;

	rep(i, 0, n)

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

	cout << sol(0, w) << endl;

}

int main() {

	ios::sync_with_stdio(0);

	cin.tie(NULL);

	cout.tie(NULL);

	int t = 1;

	//cin >> t;

	while (t--)

		solve();



#ifndef ONLINE_JUDGE

	- system("pause");

#endif



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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.773374788651675x):
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

#define rep(i,a,n) for (int i=a;i<n;i++)

#define per(i,a,n) for (int i=n-1;i>=a;i--)

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

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

#define clr(v, d) memset(v, d, sizeof(v))

#define fi first

#define se second

#define pp push_back

#define pb pop_back

#define pi 3.141592654

#define MOD 1000000007 

#define cons1 1e12

#define cons2 1e6

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int, ll> pa;

typedef unsigned long long int ull;

typedef double long dl;

const int N = 1e5+9,oo=-1e9;

ll dp[109][N], n, v[109][109];

ll sol(int i, int k){

	if (i == n)  return 0;

	if (!dp[i][k]) {

		if (k >= v[i][0])   

			dp[i][k] = v[i][1] + sol(i + 1, k - v[i][0]);

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

	}



	return dp[i][k];

}

void solve() {

	int w;

	cin >> n >> w;

	rep(i, 0, n)

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

	cout << sol(0, w) << endl;

}

int main() {

	ios::sync_with_stdio(0);

	cin.tie(NULL);

	cout.tie(NULL);

	int t = 1;

	//cin >> t;

	while (t--)

		solve();



#ifndef ONLINE_JUDGE

	- system("pause");

#endif



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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

using namespace std;

#define INF 2000000000

typedef long long int ll;

typedef pair<ll,ll> ii;

typedef vector<ll> vi;

typedef vector<ii> vii;

#define getbit(n,i) (((n)&(1<<(i)))!=0)

#define setbit0(n,i) ((n)&(~(1<<(i))))

#define setbit1(n,i) ((n)(1<<(i)))

#define togglebit(n,i) ((n)^(1<<(i)))

#define lastone(n) ((n)&(-(n)))

#define read freopen("debug\\in.txt","r",stdin)

#define write freopen("debug\\out.txt","w",stdout)

#define fi first

#define se second

#define getI(a) scanf("%d",&a)

#define getII(a,b) scanf("d",&a,&b)

#define PI (acos(-1))

#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL)

#define mod (1000000007)

#define asz 500005

#define t int t;scanf("%d",&t);for(int v=1;v<=t;v++)

#define loop_arr(i,a,b) for(int i=a;i<b;i++)

#define loop_norm(i,a,b) for(int i=a;i<=b;i++)

#define minheap priority_queue<int,vector<int>,greater<int> >

#define maaheap priority_queue<int>

#define pb push_back

#define newl "\n"

ll BIGMOD ( ll a, ll p, ll m )

{

    ll result = 1;

    ll x = a;



    while ( p )

    {

        if ( p & 1 ) //p is odd

        {

            result = ( result * x ) % m;

        }

        x = ( x * x ) % m;

        p = p >> 1;

    }



    return result;

}



bool isPrime(int n)

{

    if (n <= 1)  return false;

    if (n <= 3)  return true;

    if (n%2 == 0 || n%3 == 0) return false;



    for (int i=5; i*i<=n; i=i+6)

        if (n%i == 0 || n%(i+2) == 0)

           return false;



    return true;

}



void SieveOfEratosthenes(int n)

{

    bool prime[n+1];

    memset(prime, true, sizeof(prime));



    for (int p=2; p*p<=n; p++)

    {



        if (prime[p] == true)

        {

            for (int i=p*p; i<=n; i += p)

                prime[i] = false;

        }

    }

}

ll arr[105][2];

ll mem[105][100005];

int n,w;

ll knapsack(int i,int W )

{

    if(i==n)

    {

       return 0;

    }

    if(W==0) return 0;

    if(mem[i][W]!=-1) return mem[i][W];

    ll res1=-1,res2=-1;

   if(W>=arr[i][0])  res1=arr[i][1]+knapsack(i+1,W-arr[i][0]);

     res2=knapsack(i+1,W);

     return mem[i][W]=max(res1,res2);



}



int main()

{

   //fastread;

   //int n;

   cin>>n>>w;

   loop_arr(i,0,n)

   {

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

   }

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

   {

       for(int j=0;j<=w;j++) mem[i][j]=-1;

   }

   ll res=knapsack(0,w);

   cout<<res<<newl;



  return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

using namespace std;

#define ll long long

ll maxi(ll a,ll b)

{

    if(a>b)return a;

    return b;

}

int main(void)

{

    ll n,W;

    cin>>n>>W;

    ll ks[n+1][W+1];

    int v[n+1];

    int w[n+1];

    v[0]=w[0]=0;

    int i;

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

    {

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

    }

    int j;

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

    {

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

        {

            if(!i||!j)ks[i][j]=0;



       else if(w[i]<=j)

        {

            ks[i][j]=maxi(v[i]+ks[i-1][j-w[i]],ks[i-1][j]);



        }

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

        }

    }

    cout<<ks[n][W];

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

using namespace std;



vector<pair<int,int>> item;

long long dp[105][100005];



int n,w;



long long solve(int pos, int peso){

    

    if(peso > w) return -1000000000000000;

    if(pos > n) return -1000000000000000;

    

    if(dp[pos][peso]) return dp[pos][peso];

    

    if(pos == n){

        return 0;

    }

    

    dp[pos][peso] = max( solve(pos+1, peso), item[pos].second + solve(pos+1, peso + item[pos].first));     

    // cout << dp[pos][peso] << " " << peso << endl;

    return dp[pos][peso];

    

}



int main() {

    cin >> n >> w;

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

        pair<int, int> p; cin >>p.first >> p.second;

        item.push_back(p);

    }



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

    return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

#define ll          long long int

#define pii         pair<int,int>

#define uu          first

#define vv          second

#define fastIO      ios::sync_with_stdio(0);cin.tie(0);

using namespace std;



const int MAX = 1e6 + 6;

int main()

{

    fastIO;

    int n, W;

    cin>>n>>W;

    vector<ll>w(n+1), val(n+1);

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

    

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

    

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

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

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

            

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

        }

    }

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

    

    return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

#define inf INFINITY

#define file freopen( "input.txt" , "r" , stdin) ; freopen( "output.txt" , "w" , stdout) ;

#define Gamed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define _3102_ main()

#define endl '\n'

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

using namespace std;

const int N = 1e5 + 100;

const ll MX = 1e9;

const ll mod = 1e9 + 7;

const double eps = 1e-9 ;



ll n, tot,  w[N] , v[N] , dp[2][N]  ;



void show(){

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

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

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

		}

		cout << endl ;

	}

	cout << "--------------------\n" ;

}



int _3102_{

	Gamed

	cin >> n >> tot ;

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

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

	}

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

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

				if ( i & 1 ){

					dp[1][j] = dp[0][j] ;

					if ( j >= w[i]){

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

					}

				}

				else {

					dp[0][j] = dp[1][j] ;

					if ( j >= w[i]){

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

					}

				}

		}

	}

	cout << (n % 2 != 0 ? dp[0][tot] : dp[1][tot] )<< endl ;

	return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

#define endl '\n'

#define ll long long

using namespace std;



const int MXN = 110;

const int MXK = 100005;

int n, k;

int v[MXN], w[MXN];

ll dp[MXN][MXK];



int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> n >> k;

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

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

    }

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

    //     for(int j = k; j >= 0; j--) {

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

    //         if(j + w[i] <= k) {

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

    //         }

    //     }

    // }

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

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

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

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

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

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

            }

        }

    }

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

    return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

 

#include <algorithm>

#include <cmath>

#include <cstring>

#include <iomanip>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <stack>

#include <string>

#include <vector>

using namespace std;

typedef long long ll;

#define pii pair<ll,ll>



const ll maxn = 1e5 + 101;

ll w[maxn],v[maxn];

ll f[maxn];

int main(){

    ll n,W;

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

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

        scanf("%lld%lld",w+i,v+i);

    }

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

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

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

        }

    }

    printf("%lld\n",f[W]);

    return 0;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.7811187641577306x):
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#include<bits/stdc++.h>  

#define endl "\n"

using namespace std;

	typedef long long ll;

	const int maxn=105000;

	const int inf=0x3f3f3f3f;

	ll w[105];

	ll v[105];

	ll dp[105][maxn];

	ll n,m;

	int main(){

		IOS

		cin>>n>>m;

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

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

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

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

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

				if(j+w[i-1]<=m){

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

				}

			}

				

					

		}

		ll ans=-1;

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

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

		cout<<ans<<endl;

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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

long long dp[maxn];

long long w[maxn],v[maxn];

int main()

{

   int n,m;

   cin>>n>>m;

   memset(dp,0,sizeof(dp));

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

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

   }

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

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

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

       }

   }

   cout<<dp[m]<<endl;

   return 0;

}


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

#include<cmath>

#include<cstring>

using namespace std;

const int maxn=105;

const int maxw=1e5+5;

const int inf=0x3f3f3f3f;

int w[maxn],v[maxn];

long long dp[maxw][maxn];

int main()

{

	int n,tw;

	while(~scanf("%d%d",&n,&tw))

	{

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

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

		for(int i=1;i<=n;i++)//n件物品 

		{

			for(int j=0;j<=tw;j++)//背包容量 

			{

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

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

				else

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

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

			}

			//cout<<endl;

		}

		cout<<dp[tw][n];

	}

}
// Slower C++ solution:
//01背包 

#include<bits/stdc++.h>

using namespace std;



const int N = 105;

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

long long v[N];//价值

int w[N];//重量

int n,m;

 

int main()

{

 	cin>>n;//物品种数

	cin>>m;//背包容量

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

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

	}

	

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

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

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

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

		}

	}

	cout<<f[m]<<endl;

	return 0;

} 

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

#include<cmath>

#include<cstring>

using namespace std;

const int maxn=105;

const int maxw=1e5+5;

const int inf=0x3f3f3f3f;

int w[maxn],v[maxn];

long long dp[maxw][maxn];

int main()

{

	int n,tw;

	while(~scanf("%d%d",&n,&tw))

	{

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

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

		for(int i=1;i<=n;i++)//n件物品 

		{

			for(int j=0;j<=tw;j++)//背包容量 

			{

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

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

				else

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

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

			}

			//cout<<endl;

		}

		cout<<dp[tw][n];

	}

}