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

using namespace std;

typedef long long ll;

#define fast ios_base::sync_with_stdio(false),cin.tie(NULL)

#define x first

#define y second



vector<vector<int>> dp, arr;

int main() {

    fast;

    int n, w;

    cin>>n>>w;

    vector<int> weight(n), value(n);

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

        cin>>weight[i]>>value[i];

    }

    ll dp[n+1][w+1];

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

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

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

                dp[i][j] = 0;

            else{

                ll leave = dp[i-1][j], take = -1;

                if(weight[i-1] <= j)

                    take = dp[i - 1][j - weight[i-1]] + value[i-1];

                dp[i][j] = max(take, leave);

            }



        }

    }

    cout<<dp[n][w];

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

		scanf("%lld%lld",&w,&v);

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

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

			}

		}

	}

	ans=0;

	for (int i=mxw;i>=1;i--){

		ans=max(ans,val[i]);

	}

	printf("%lld\n",ans);

	return 0;

} 

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

#define Joe ios::sync_with_stdio(0); cin.tie(NULL); ios_base::sync_with_stdio(0); cout.tie(NULL);

#define INF 1e9+7

const long long N =1e5+5;

using namespace std;

int main(){

	Joe

	int n,w;

	cin>>n>>w;

	long long weight[n+5],price[n+5];

	long long arr[n+5][w+5];

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

		cin>>weight[i];

		cin>>price[i];

	}

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

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

			if(r==0||w==0)

				arr[r][c]=0;

			else if(weight[r]<=c)

				arr[r][c]=max(arr[r-1][c],price[r]+arr[r-1][c-weight[r]]);

			else

				arr[r][c]=arr[r-1][c];

		}

	}

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

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

		scanf("%lld%lld",&w,&v);

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

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

			}

		}

	}

	ans=0;

	for (int i=mxw;i>=1;i--){

		ans=max(ans,val[i]);

	}

	printf("%lld\n",ans);

	return 0;

} 

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

using namespace std;

int main()

{

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

  int n,c;

  cin>>n>>c;

  int val[n+1],w[n+1];

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

    cin>>w[i]>>val[i];

    long long dp[n+5][c+5];

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

        dp[0][j]=0;

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

  {

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

      {

          if(j==0)

            dp[i][j]=0;

          else if(w[i]<=j)

          {

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

          }

          else

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

      }

  }

  cout<<dp[n][c];

   return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

		scanf("%lld%lld",&w,&v);

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

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

			}

		}

	}

	ans=0;

	for (int i=mxw;i>=1;i--){

		ans=max(ans,val[i]);

	}

	printf("%lld\n",ans);

	return 0;

} 

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

using namespace std;

#define ll long long

#define pb push_back

#define F first

#define S second

const int mod = 1e9+7, A = 1e2+5;

int n, w, weight[A], val[A];

ll dp[A][100005];

ll build()

{

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

	{

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

		{

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

			

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

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

			

			dp[i][j] = ret;

		}

	}

	return dp[n][w];

}



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 >> weight[i] >> val[i];

	cout << build();

	return 0;

}

	/*



	states : indx , weight



	base case : dp[0][ay 7aga] = 0, dp[ay 7aga][0] = 0



	transitions : dp[i][j] = dp[i-1][j]  |  dp[i-1][j-w] + val



	0   0



	3   30

		

	4   50

	

	5   60

	

	

	 */


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

		scanf("%lld%lld",&w,&v);

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

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

			}

		}

	}

	ans=0;

	for (int i=mxw;i>=1;i--){

		ans=max(ans,val[i]);

	}

	printf("%lld\n",ans);

	return 0;

} 

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



#define ll long long

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

#define pb push_back

const long double pi=3.141592654;

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

using namespace std;



const ll inf = 1e9 +5, mod = 1e9+7,N = 1e5+5;



    int val[N],weights[N];

    ll dp[102][N];

int main()

{

    OSOS

	ll n,w;

    cin>>n>>w;



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

    	cin>>weights[i]>>val[i];



    for(int rem = 1; rem <= w; rem++)

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

    	{

    		ll op1,op2;

    		op1 = dp[item-1][rem];

    		op2 = 0;

    		if(rem >= weights[item])

    		{

    			op2 = val[item] + dp[item-1][rem - weights[item]];

    		}

    		dp[item][rem] = max(op1,op2);

    	}



    cout<<dp[n][w];



    return 0;

}




// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

		scanf("%lld%lld",&w,&v);

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

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

			}

		}

	}

	ans=0;

	for (int i=mxw;i>=1;i--){

		ans=max(ans,val[i]);

	}

	printf("%lld\n",ans);

	return 0;

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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 (n-i&&!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



}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

		scanf("%lld%lld",&w,&v);

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

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

			}

		}

	}

	ans=0;

	for (int i=mxw;i>=1;i--){

		ans=max(ans,val[i]);

	}

	printf("%lld\n",ans);

	return 0;

} 

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

#define ull unsigned long long

#define ll long long

#define pb push_back

#define endl '\n'

#define line cout<<"----------------------"<<endl

#define mp make_pair

#define mod 1000000007

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

#define filein freopen("input.txt","r",stdin)

#define fileout freopen("output.txt","w",stdout)

using namespace std;

const ll  mx=300009;

vector<pair<ll ,ll > > v;

ll  dp[100001][109];

int main()

{

    ll  n,w;

    cin>>n>>w;

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

    {

        ll  a,b;

        cin>>a>>b;

        v.pb(mp(a,b));

    }

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

    {



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

        {

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

            if(v[j].first>i) continue;

            dp[i][j]=max(dp[i][j],dp[i-v[j].first][j-1]+v[j].second);

        }

    }

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

}

/*

3 5

3 3

4 2

2 4

*/


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

 

long long n,val[100005],w,v,k,mxw,ans;

bool dp[100005]; 

int main(){

	dp[0]=true;

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

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

		scanf("%lld%lld",&w,&v);

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

			if (dp[j]== true && j+w <= mxw){

				dp[j+w]=true;

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

			}

		}

	}

	ans=0;

	for (int i=mxw;i>=1;i--){

		ans=max(ans,val[i]);

	}

	printf("%lld\n",ans);

	return 0;

} 

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

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

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

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

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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

#define eps 1e-3

#define pi acos(-1.0)

#define inf 0x3f

#define INF 0x3f3f3f3f

#define pb push_back

#define debug1 cout<<"&&";

#define debug2 cout<<"**";

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

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

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

using namespace std;

typedef double db;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pii;

typedef pair<long long, int> pli;

typedef pair<long long, long long> pll;

const int mod = 1e9 + 7;

const int N = 1e5+10;

const int M = 1e6+10;

inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

inline ll Pow(ll a, ll b) { ll ans = 1; for( ; b; b >>= 1) { if(b&1) ans = ans * a % mod; a = a * a % mod;} return ans;}

inline ll Mul ( ll a, ll b)  { ll lf = a * ( b >> 25ll ) % mod * ( 1LL << 25 ) % mod; ll rg = a * ( b & ( ( 1ll << 25 ) - 1 ) ) % mod; return ( lf + rg ) % mod;}

//==================================================================================================================================================================//



ll n, W, dp[N];



int main() {

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

   for1(i, n) {

      ll w, v;

      scanf("%lld %lld", &w, &v);

      for(ll j = W; j >= w; --j) {

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

      }

   }

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

   return 0;

}

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

using namespace std;

typedef long long ll;

const ll max_n=1e5+100;

const ll inf=0x3f3f3f3f;

ll t,n,m,p[max_n],v[max_n],q[max_n],dp[max_n];

int main(){

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

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    while(cin>>n>>m){

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

            cin>>p[i]>>q[i];

        }

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

        ll ans=0;

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

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

                dp[j]=max(dp[j],dp[j-p[i]]+q[i]);

                ans=max(ans,dp[j]);

            }

        }cout<<ans<<endl;

    }

    return 0;

}


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

#define eps 1e-3

#define pi acos(-1.0)

#define inf 0x3f

#define INF 0x3f3f3f3f

#define pb push_back

#define debug1 cout<<"&&";

#define debug2 cout<<"**";

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

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

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

using namespace std;

typedef double db;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pii;

typedef pair<long long, int> pli;

typedef pair<long long, long long> pll;

const int mod = 1e9 + 7;

const int N = 1e5+10;

const int M = 1e6+10;

inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

inline ll Pow(ll a, ll b) { ll ans = 1; for( ; b; b >>= 1) { if(b&1) ans = ans * a % mod; a = a * a % mod;} return ans;}

inline ll Mul ( ll a, ll b)  { ll lf = a * ( b >> 25ll ) % mod * ( 1LL << 25 ) % mod; ll rg = a * ( b & ( ( 1ll << 25 ) - 1 ) ) % mod; return ( lf + rg ) % mod;}

//==================================================================================================================================================================//



ll n, W, dp[N];



int main() {

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

   for1(i, n) {

      ll w, v;

      scanf("%lld %lld", &w, &v);

      for(ll j = W; j >= w; --j) {

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

      }

   }

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

   return 0;

}

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

using namespace std;



typedef long long ll;



const int maxn = 105, maxw = 1e5 + 5;



int main(int argc, const char * argv[])

{

    ll n, W, w[maxn], v[maxn], dp[maxw] = {0};

    cin >> n >> W;

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

        scanf("%lld %lld", &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;

    return 0;

}

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

#define eps 1e-3

#define pi acos(-1.0)

#define inf 0x3f

#define INF 0x3f3f3f3f

#define pb push_back

#define debug1 cout<<"&&";

#define debug2 cout<<"**";

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

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

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

using namespace std;

typedef double db;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> pii;

typedef pair<long long, int> pli;

typedef pair<long long, long long> pll;

const int mod = 1e9 + 7;

const int N = 1e5+10;

const int M = 1e6+10;

inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

inline ll Pow(ll a, ll b) { ll ans = 1; for( ; b; b >>= 1) { if(b&1) ans = ans * a % mod; a = a * a % mod;} return ans;}

inline ll Mul ( ll a, ll b)  { ll lf = a * ( b >> 25ll ) % mod * ( 1LL << 25 ) % mod; ll rg = a * ( b & ( ( 1ll << 25 ) - 1 ) ) % mod; return ( lf + rg ) % mod;}

//==================================================================================================================================================================//



ll n, W, dp[N];



int main() {

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

   for1(i, n) {

      ll w, v;

      scanf("%lld %lld", &w, &v);

      for(ll j = W; j >= w; --j) {

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

      }

   }

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

   return 0;

}

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

#include<vector>

#include<string.h>

using namespace std;

long long dp[100005];

int N, W;

struct Item{

    int weight;

    int value;

};

vector <Item> item;

int main(int argc, char const *argv[])

{

    int temp1, temp2;

    cin >> N >> W;

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

        cin >> temp1 >> temp2;

        item.push_back({temp1, temp2});

    }

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

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

        int temp_w = item[i].weight;

        int temp_v = item[i].value;

        for(int j = W ; j>=temp_w ; j--){

            dp[j] = max(dp[j], dp[j - temp_w] + temp_v);

            

        }

    }

    cout << dp[W] << endl;

}

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

using namespace std;

#define LL   long long

#define LIM  100000

#define SZ   100



LL n, capacity, dp[SZ+5][LIM+5], weight[SZ+5], val[SZ+5];

bool vis[SZ+5][LIM+5];





LL f(LL in, LL rem){

    if(in > n || rem < 0) return 0;



    if(vis[in][rem]) return dp[in][rem];

    vis[in][rem] = 1;

    LL take = 0, notTake;

    if(rem-weight[in] >= 0) take = val[in] + f(in+1, rem-weight[in]);

    notTake = f(in+1, rem);

    return dp[in][rem] = max(take, notTake);

}



int main(){

    cin>>n>>capacity;

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

    LL res = f(1, capacity);

    cout<<res<<'\n';

}






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

using namespace std;



const long long inf = (long long) 1e9 * 100 + 5;

const int maxn = 105, maxm = (int) 1e5 + 5;

long long dp[maxn][maxm] = {0};

bool vis[maxn][maxm];

int n, w;

int we[maxn];

long long v[maxn];



long long solve(int i, int weight) {

    if (i == n) return 0;

    if (vis[i][weight]) return dp[i][weight];

    long long ans = solve(i + 1, weight);

    if (weight + we[i] <= w) ans = max(ans, solve(i + 1, weight + we[i]) + v[i]);

    vis[i][weight] = true;

    return dp[i][weight] = ans;

}

int main() {

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

    cin >> n >> w;

    for (int i = 0; i < n; ++i) cin >> we[i] >> v[i];

    memset(vis, false, sizeof(vis));

    cout << solve(0, 0) << '\n';

    return 0;

}




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

using namespace std;



int main() {

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

    int n, w;

    cin >> n >> w;

    vector<int> we(n), v(n);

    for (int i = 0; i < n; ++i) cin >> we[i] >> v[i];

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

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

        for (int weight = w - we[i]; weight >= 0; --weight)

            dp[weight + we[i]] = max(dp[weight + we[i]], dp[weight] + v[i]);

    cout << *max_element(dp.begin(), dp.end()) << '\n';

    return 0;

}




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

Educational DP Contest - D - Knapsack 1

https://atcoder.jp/contests/dp/tasks/dp_d

*/



#include <bits/stdc++.h>

using namespace std; 

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

typedef long long ll; 

 

int main()  

{ 

    FAST_INP;

    ll n,W,w,v;

    cin >> n >> W;

    ll dp[100005];

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

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

    	cin >> w >> v;

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

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

		}	

	}

	cout << dp[W] << endl;

    return 0;

} 


// Optimized solution to the same problem (faster):
/*

Educational DP Contest - D - Knapsack 1

https://atcoder.jp/contests/dp/tasks/dp_d

*/



#include <bits/stdc++.h>

using namespace std; 

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

typedef long long ll; 

 

int main()  

{ 

    FAST_INP;

    ll n,W,w,v;

    cin >> n >> W;

    ll dp[W+1];

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

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

    	cin >> w >> v;

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

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

		}	

	}

	cout << dp[W] << endl;

    return 0;

} 


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

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

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

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

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

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

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

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



int main() {

  ll n, ww;

  cin >> n >> ww;

  vll w(n), v(n);

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

  vll dp(100001, 0);

  vector<vll> check(100001, vll(0));

  vll x(n, 0);

  check[0] = x;

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

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

    ll memo = -1;

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

      if (i < w[j]) continue;

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

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

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

        memo = j;

      }

    }

    if (memo != -1) {

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

      check[i][memo] = 1;

    }

    else check[i] = check[i - 1];

  }

  cout << dp[ww] << endl;

}

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

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

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

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

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

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

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

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



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

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



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

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

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

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

  }

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

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

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

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

    }

  }

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

}

// Fastest known solution for this problem: