stablegradients/pie-gem5-pairs huggingface dataset:
// 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.3455906946629743x):
#include<bits/stdc++.h>

#define ll long long

#define pb push_back

#define pf push_front

#define pob pop_back

#define pof pop_front

#define scn(n) scanf("%d",&n)

#define scnll(n) scanf("%lld",&n)

#define nl printf("\n")

#define YES printf("YES\n")

#define Yes printf("Yes\n")

#define yes printf("yes\n")

#define NO printf("NO\n")

#define No printf("No\n")

#define no printf("no\n")

using namespace std;

int n;

ll mn=-10000000000000;

ll dp[100002][2]={0};

ll w[101],v[101];

ll solve(int weight){

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

        int prev=i%2;

        int now=(i+1)%2;

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

            if(w[i]>j) dp[j][now]=dp[j][prev];

            else dp[j][now]=max(dp[j-w[i]][prev]+v[i],dp[j][prev]);

        }

    }

    return dp[weight][(n+1)%2];

}

int main(){

    scn(n);

    int wt;scn(wt);

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

        scnll(w[i]);

        scnll(v[i]);

    }

    ll ans=solve(wt);

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

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

#define ll long long

using namespace std;

#define inf 0x3f3f3f3f 

int main(){

	ll  n , W; cin >> n >> W;

    ll w[101] , v[101] , dp[100001] = {0};

    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;

}

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

#define ll long long

#define pb push_back

#define pf push_front

#define pob pop_back

#define pof pop_front

#define scn(n) scanf("%d",&n)

#define scnll(n) scanf("%lld",&n)

#define nl printf("\n")

#define YES printf("YES\n")

#define Yes printf("Yes\n")

#define yes printf("yes\n")

#define NO printf("NO\n")

#define No printf("No\n")

#define no printf("no\n")

using namespace std;

int n;

ll mn=-10000000000000;

ll dp[100002][2]={0};

ll w[101],v[101];

ll solve(int weight){

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

        int prev=i%2;

        int now=(i+1)%2;

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

            if(w[i]>j) dp[j][now]=dp[j][prev];

            else dp[j][now]=max(dp[j-w[i]][prev]+v[i],dp[j][prev]);

        }

    }

    return dp[weight][(n+1)%2];

}

int main(){

    scn(n);

    int wt;scn(wt);

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

        scnll(w[i]);

        scnll(v[i]);

    }

    ll ans=solve(wt);

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

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

using namespace std;

typedef long long ll;





ll w[105],f[100005];

ll v[105];



signed main()

{

	ll N,W;

	while(cin>>N>>W){

		for(ll i=1;i<=N;i++)

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

		

		//01背包 

		memset(f,0,sizeof f);

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

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

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

		}	

		

		cout<<f[W]<<endl;

	}

}

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

#define ll long long

#define pb push_back

#define pf push_front

#define pob pop_back

#define pof pop_front

#define scn(n) scanf("%d",&n)

#define scnll(n) scanf("%lld",&n)

#define nl printf("\n")

#define YES printf("YES\n")

#define Yes printf("Yes\n")

#define yes printf("yes\n")

#define NO printf("NO\n")

#define No printf("No\n")

#define no printf("no\n")

using namespace std;

int n;

ll mn=-10000000000000;

ll dp[100002][2]={0};

ll w[101],v[101];

ll solve(int weight){

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

        int prev=i%2;

        int now=(i+1)%2;

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

            if(w[i]>j) dp[j][now]=dp[j][prev];

            else dp[j][now]=max(dp[j-w[i]][prev]+v[i],dp[j][prev]);

        }

    }

    return dp[weight][(n+1)%2];

}

int main(){

    scn(n);

    int wt;scn(wt);

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

        scnll(w[i]);

        scnll(v[i]);

    }

    ll ans=solve(wt);

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

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

using namespace std;



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

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

#define fn(i,a,b) for(int i=a ; i>=b ; i--)

#define pb push_back

#define mk make_pair

#define ff first

#define ss second

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



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;

typedef vector<ll> vll;



const int M=1e5+5;

const ll INF=1e15;

const int MOD=1e9+5;



int n,W;

ll dp[M][105],valor[105],peso[105];



ll ks(int w,int x){

  if (w < 0) return -INF;

  if (x > n) return 0;

  if (dp[w][x] != -1) return dp[w][x];

  dp[w][x] = max(ks(w,x+1) , valor[x] + ks(w-peso[x],x+1));

  return dp[w][x];

}



void ini(){

  fp(i,0,M)

    fp(j,1,n+1) dp[i][j] = -1;

}



int main(){



	fastio;

  cin >> n >> W;

  ini();

  fp(i,1,n+1) cin >> peso[i] >> valor[i];

  cout << ks(W,1) << "\n";



	return 0;

}


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

#define ll long long

#define pb push_back

#define pf push_front

#define pob pop_back

#define pof pop_front

#define scn(n) scanf("%d",&n)

#define scnll(n) scanf("%lld",&n)

#define nl printf("\n")

#define YES printf("YES\n")

#define Yes printf("Yes\n")

#define yes printf("yes\n")

#define NO printf("NO\n")

#define No printf("No\n")

#define no printf("no\n")

using namespace std;

int n;

ll mn=-10000000000000;

ll dp[100002][2]={0};

ll w[101],v[101];

ll solve(int weight){

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

        int prev=i%2;

        int now=(i+1)%2;

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

            if(w[i]>j) dp[j][now]=dp[j][prev];

            else dp[j][now]=max(dp[j-w[i]][prev]+v[i],dp[j][prev]);

        }

    }

    return dp[weight][(n+1)%2];

}

int main(){

    scn(n);

    int wt;scn(wt);

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

        scnll(w[i]);

        scnll(v[i]);

    }

    ll ans=solve(wt);

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

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

//#pragma GCC optimize("Ofast")

//#pragma GCC target("avx,avx2,fma")



using namespace std;



typedef long long ll;



//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>pb_ds;



#define IN freopen("in.txt","r",stdin)

#define OUT freopen("out.txt","w",stdout)

#define pi pair<int,int>

#define F first

#define S second

#define pb push_back

#define pp pop_back

#define mod 1000000007

#define pai acos(-1)

#define N 100005



ll Weight[N],Profit[N],dp[2][N];



int main ()

{

   ios_base::sync_with_stdio(false);

   cin.tie(NULL);

   int n,w;cin>>n>>w;

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

      cin>>Weight[i]>>Profit[i];

   }

   fill(dp[0],dp[0]+2*N,-INT_MAX*105);

   dp[(n+1)%2][0]=0;

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

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

         ll op1=dp[(i+1)%2][s];

         ll op2=(s-Weight[i]>=0)?Profit[i]+dp[(i+1)%2][s-Weight[i]]:0ll;

         dp[i%2][s]=max(op1,op2);

      }

   }

   ll ans=0;

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

   cout<<ans<<"\n";

   return 0;

}




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

#define ll long long

#define pb push_back

#define pf push_front

#define pob pop_back

#define pof pop_front

#define scn(n) scanf("%d",&n)

#define scnll(n) scanf("%lld",&n)

#define nl printf("\n")

#define YES printf("YES\n")

#define Yes printf("Yes\n")

#define yes printf("yes\n")

#define NO printf("NO\n")

#define No printf("No\n")

#define no printf("no\n")

using namespace std;

int n;

ll mn=-10000000000000;

ll dp[100002][2]={0};

ll w[101],v[101];

ll solve(int weight){

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

        int prev=i%2;

        int now=(i+1)%2;

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

            if(w[i]>j) dp[j][now]=dp[j][prev];

            else dp[j][now]=max(dp[j-w[i]][prev]+v[i],dp[j][prev]);

        }

    }

    return dp[weight][(n+1)%2];

}

int main(){

    scn(n);

    int wt;scn(wt);

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

        scnll(w[i]);

        scnll(v[i]);

    }

    ll ans=solve(wt);

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

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

using namespace std;

int main(){

  int n,w;

  cin>>n>>w;

 	vector<long long> dp(200005);

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

  {

    int a,b;

    cin>>a>>b;

    for(int j=w-a;j>=0;j--)

    {

      dp[j+a]=max(dp[j+a],dp[j]+b);

    }

  }

  cout<<dp[w]<<" ";

  return 0;

}


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

#define ll long long

#define dbl double

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

#define forpn(p,n,k) for(int i=p;i<n;i+=k)

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

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

using namespace std;

int no_of_bits(long long n)

{

    int count=0;

    while(n>0)

    {

        n=n>>1;

        count++;

    }

    return count;

}

long long gcd(int a,int b)

{

    if(b==0) return a;

    else return gcd(b,a%b);

}

bool isPrime(int n) {

    

    if (n == 1) {

        return false;

    }



    int i = 2;

  

    while (i*i <= n) {

        

        if (n % i == 0) {

            

            return false;

        }

        i += 1;

    }

    

    return true;

}

int main()

{   ios::sync_with_stdio(0);

    int t;

    // cin>>t;

    t=1;

    cin.tie(0);

    cout.tie(0);

    while(t--)

    {

       int n,w;

       cin>>n>>w;

      vector<ll> dp(w+1);

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

      {

        ll a,b;

        cin>>a>>b;

        for(ll j=w-a;j>=0;j--)

        {

          dp[j+a]=max(dp[j+a],dp[j]+b);

        }

      }

      cout<<dp[w]<<endl;

	}

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

using namespace std;

int main(){

  int n,w;

  cin>>n>>w;

 	vector<long long> dp(200005);

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

  {

    int a,b;

    cin>>a>>b;

    for(int j=w-a;j>=0;j--)

    {

      dp[j+a]=max(dp[j+a],dp[j]+b);

    }

  }

  cout<<dp[w]<<" ";

  return 0;

}


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

using namespace std;

int main(){

  long long n,w;

  cin>>n>>w;

 long long a[n][2];

 

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

//   dp[0]=0;

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

     long long a,b;

     cin>>a>>b;

     for(long long j=w-a;j>=0;j--){

         dp[j+a]=max(dp[j+a],dp[j]+b);

     }

 }

 cout<<dp[w]<<endl;

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

using namespace std;

int main(){

  int n,w;

  cin>>n>>w;

 	vector<long long> dp(200005);

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

  {

    int a,b;

    cin>>a>>b;

    for(int j=w-a;j>=0;j--)

    {

      dp[j+a]=max(dp[j+a],dp[j]+b);

    }

  }

  cout<<dp[w]<<" ";

  return 0;

}


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

using namespace std;

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

  if(a>b) return a;

  else return b;}

int main(){

  int n,w;

  cin>>n>>w;

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

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

  {

    long long a,b;

    cin>>a>>b;

    for(int j=w-a;j>=0;j--)

      dp[j+a]=max(dp[j+a],dp[j]+b);

  	}



  cout<<dp[w]<<endl;

}
// Slower C++ solution:


#include<iostream>

#include<string>

#include<cstdio>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#include<vector>

#include<utility>

#include<queue>

#include<stack>

#include<set>

#include<map>

#include<unordered_set>

#include<unordered_map>

#include<bitset>

using namespace std;

#define INF 2147483647

#define lINF 9223372036854775807

#define MODE 1

#ifdef MODE

#define DEB(X) cout<< #X <<": "<<X<<" ";

#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";

#define END cout<<endl;

#else

#define DEB(X) {}

#define ARDEB(i,X) {}

#define END {}

#endif

typedef long long int ll;



ll n,W,w[111],v[111],m[111][111111];

ll dp(int i,int j){//番号,重さ

	if(m[i][j]!=-1)return m[i][j];

	if(i==n)return 0;

	

	ll sum=0;

	if(j<w[i]){

		sum=dp(i+1,j);

	}

	else{

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

	}

	

	return m[i][j]=sum;

	

}



int main(){

	

	cin>>n>>W;

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

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

			m[i][j]=-1;

		}

	}

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

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

	}

	cout<<dp(0,W)<<endl;

	return 0;



}

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

#include<string>

#include<cstdio>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#include<vector>

#include<utility>

#include<queue>

#include<stack>

#include<set>

#include<map>

#include<unordered_set>

#include<unordered_map>

#include<bitset>

using namespace std;

#define INF 1000000007

#define LINF 100000000000000007

#define MOD 1000000007

#define int long long

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

#define repb(i, n) for (int i = n - 1; i >= 0; i--)

#define MODE 1

#ifdef MODE

#define DEB(X) cout<< #X <<": "<<X<<" ";

#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";

#define END cout<<endl;

#else

#define DEB(X) {}

#define ARDEB(i,X) {}

#define END {}

#endif

typedef long long ll;

typedef pair<int,int> P;

struct edge{int to,cost;};

int ceil2(int a,int b){if(a%b){return a/b+1;}else{return a/b;}}

using namespace std;



int ans;

string s;

int N,W,dp[111111][111],w[111111],v[111111];

signed main(){

	 cin>>N>>W;

	 rep(i,N)cin>>w[i]>>v[i];

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

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

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

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

	 	}

	 }

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

}
// Slower C++ solution:


#include<iostream>

#include<string>

#include<cstdio>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#include<vector>

#include<utility>

#include<queue>

#include<stack>

#include<set>

#include<map>

#include<unordered_set>

#include<unordered_map>

#include<bitset>

using namespace std;

#define INF 2147483647

#define lINF 9223372036854775807

#define MODE 1

#ifdef MODE

#define DEB(X) cout<< #X <<": "<<X<<" ";

#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";

#define END cout<<endl;

#else

#define DEB(X) {}

#define ARDEB(i,X) {}

#define END {}

#endif

typedef long long int ll;



ll n,W,w[111],v[111],m[111][111111];

ll dp(int i,int j){//番号,重さ

	if(m[i][j]!=-1)return m[i][j];

	if(i==n)return 0;

	

	ll sum=0;

	if(j<w[i]){

		sum=dp(i+1,j);

	}

	else{

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

	}

	

	return m[i][j]=sum;

	

}



int main(){

	

	cin>>n>>W;

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

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

			m[i][j]=-1;

		}

	}

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

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

	}

	cout<<dp(0,W)<<endl;

	return 0;



}

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

#include<string>

#include<cstdio>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#include<vector>

#include<utility>

#include<queue>

#include<stack>

#include<set>

#include<map>

#include<unordered_set>

#include<unordered_map>

#include<bitset>

using namespace std;

#define INF 2000000007

#define LINF 100000000000000007

#define MOD 1000000007

#define int long long

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

#define repb(i, n) for (int i = n - 1; i >= 0; i--)

#define MODE 0

#ifdef MODE

#define DEB(X) cout<< #X <<": "<<X<<" ";

#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";

#define END cout<<endl;

#else

#define DEB(X) {}

#define ARDEB(i,X) {}

#define END {}

#endif

typedef long long ll;

typedef pair<int,int> P;

struct edge{int to,cost;};

int ceil2(int a,int b){if(a%b){return a/b+1;}else{return a/b;}}

using namespace std;



int n,W,ans;

int dp[111][111111];

int w[1111],v[1111];

signed main(){

	cin>>n>>W;

	rep(i,n)cin>>w[i]>>v[i];

	rep(j,W+1){

		rep(i,n){

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

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

			

		}

	}

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

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

using namespace std;

#define MAXN 100005

typedef long long LL;



LL dp[105][MAXN];



int main()

{

	int n, w, wei, val;

	cin >> n >> w;

	

	fill(dp[0]+1, dp[0]+MAXN, -LLONG_MAX);

	

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

	{

		cin >> wei >> val;

		

		copy(dp[i-1], dp[i-1]+w, dp[i]); // ¤W¦æªº¸ê®Æáàµ§¦Ü¦¹ 

		

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

		{

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

		}

	}



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

    {

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

    	{

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

		}

		cout << "\n";

	}*/

	

	cout << *max_element(dp[n]+1, dp[n]+w+1) << "\n";

}

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

using namespace std;

#define MAXN 100005

typedef long long LL;



LL pre[MAXN], cur[MAXN];



int main()

{

	int n, w, wei, val;

	cin >> n >> w;

	

	fill(pre+1, pre+w+1, -LLONG_MAX);

	

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

	{

		cin >> wei >> val;

		

		copy(pre, pre+w+1, cur);

		

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

		{

			cur[j] = max(pre[j], pre[j-wei]+val);

		}

		

		copy(cur, cur+w+1, pre);

	}

	

	cout << *max_element(cur+1, cur+w+1) << "\n";

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

using namespace std;

#define MAXN 100005

typedef long long LL;



LL dp[105][MAXN];



int main()

{

	int n, w, wei, val;

	cin >> n >> w;

	

	fill(dp[0]+1, dp[0]+MAXN, -LLONG_MAX);

	

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

	{

		cin >> wei >> val;

		

		copy(dp[i-1], dp[i-1]+w, dp[i]); // ¤W¦æªº¸ê®Æáàµ§¦Ü¦¹ 

		

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

		{

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

		}

	}



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

    {

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

    	{

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

		}

		cout << "\n";

	}*/

	

	cout << *max_element(dp[n]+1, dp[n]+w+1) << "\n";

}

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

using namespace std;

#define MAXN 100005

typedef long long LL;



LL pre[MAXN], cur[MAXN];



int main()

{

	int n, w, wei, val;

	cin >> n >> w;

	

	fill(pre+1, pre+w+1, -LLONG_MAX);

	

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

	{

		cin >> wei >> val;

		

		//copy(pre, pre+w+1, cur);

		

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

		{

			cur[j] = max(pre[j], pre[j-wei]+val);

		}

		

		copy(cur, cur+w+1, pre);

	}

	

	cout << *max_element(cur+1, cur+w+1) << "\n";

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

#include <iostream>



using namespace std;



#define fo(i,CApiTaL_N) for(int i=0; i<CApiTaL_N; i++)

#define Fo(i,k,CApiTaL_N) for(int i=k; i<CApiTaL_N; i++)

#define ll long long

#define pb push_back

#define mp make_pair

#define F first

#define S second

#define clr(x) memset(x, 0, sizeof(x))

#define tr(it, a) for(auto it=a.begin(); it!=a.end(); it++)

#define PI 3.1415926535897932384626

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

typedef vector<int> vi;

typedef vector<ll> vl;

typedef vector<pii> vpii;

typedef vector<pll> vpll;

typedef vector<vi> vvi;

typedef vector<vl> vvl;



int t=1;

const int mxW=1e5, mxN=1e2, mxV=1e9;

int n,w;

vl wi(mxN+1),v(mxN+1),dp(mxW+1);



void test_case(){

    cin>>n>>w;

    Fo(i,1,n+1){

        cin>>wi[i]>>v[i];

    }

    Fo(j,1,n+1){

        for(int i=w; i>=0; i--){

            if(i-wi[j]<0)continue;

            // cout<<i<<" "<<j<<" "<<dp[i]<<" "<<i-wi[j]<<" "<<dp[i-wi[j]]<<" "<<v[j]<<endl;

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

        }

    }

    cout<<dp[w]<<endl;

}



int main() {

    ios_base::sync_with_stdio(false);

	cin.tie(NULL);



    // cin>>t;

    while(t--){

        test_case();

    }

    

    return 0;

}

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

#include <bits/stdc++.h>



using namespace std;



using ll=long long;

const int INF = 1e9+5;



void max_self(ll &a, ll b){

    a=max(a,b);

}



int main() {

    ios_base::sync_with_stdio(0);

    cin.tie(NULL);



    int n,w;

    cin>>n>>w;

    vector<ll>dp(w+1);

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

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

        int wei, val;

        cin>>wei>>val;

        for(int curr=w-wei; curr>=0; curr--){

            max_self(dp[curr+wei],dp[curr]+(ll)val);

        }

    }

    cout<<dp[w]<<endl;



    return 0;

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

#define MAX 100005

using namespace std;

 

int main(){

  int n, mn = 0, t = 0, u = 0;

  string s;

  cin >> n >> s;

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

    t += (s[i-1] == 'W') + (s[i] == 'W') - 1;

    u += (s[i] == 'E');

    mn = min(mn, t);

  }

  printf("%d\n", u+mn);

}

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

#include <algorithm>

#define MAX 300005

using namespace std;



int main(){

    int n, mn = 0, t = 0, u = 0;

    char s[MAX];

    scanf("%d\n%s", &n, s);

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

        t += (s[i-1] == 'W') + (s[i] == 'W') - 1;

        u += (s[i] == 'E');

        mn = min(mn, t);

    }

    printf("%d\n", u+mn);

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



const int MAX_N = 300000;



int main() {

	int N;

	std::string S;

	std::cin >> N >> S;



	std::vector<int> left(MAX_N), right(MAX_N), cost(MAX_N);

	int cnt;



	cnt = 0;

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

		left[i] = cnt;

		if(S[i] == 'W') ++cnt;

	}



	cnt = 0;

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

		right[i] = cnt;

		cost[i] = left[i] + right[i];

		if(S[i] == 'E') ++cnt;

	}



	std::sort(cost.begin(), cost.begin() + N);



	std::cout << cost[0] << std::endl;

 }


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



const int MAX_N = 300000;



// int left[MAX_N], right[MAX_N], cost[MAX_N];



int main() {

	int N;

	std::string S;

	std::cin >> N >> S;



	// std::vector<int> left(MAX_N), right(MAX_N), cost(MAX_N);

	static int left[MAX_N], right[MAX_N], cost[MAX_N];

	int cnt;



	cnt = 0;

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

		left[i] = cnt;

		if(S[i] == 'W') ++cnt;

	}



	cnt = 0;

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

		right[i] = cnt;

		cost[i] = left[i] + right[i];

		if(S[i] == 'E') ++cnt;

	}



	// std::sort(cost.begin(), cost.begin() + N);

	std::sort(cost, cost + N);



	std::cout << cost[0] << std::endl;

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

#include<cmath>

using namespace std;

int main()

{

	int n,ce=0,cw=0,an=1e9,a[300003];

	char c[300003];

	cin>>n;

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

	{

		cin>>c[i];

		a[i]=cw;

		if(c[i]=='W')cw++;

	}

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

	{

		an=min(an,a[i]+ce);

		if(c[i]=='E')ce++;

	}

	cout<<an<<endl;

	return 0;

}

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

int n,i,e,w,s=1e9,a[1<<19];char c[1<<19];main(){for(scanf("%d\n",&n);i<n;scanf("%c",c+i),a[i]=w,w+=c[i++]==87);for(;i>0;s=s<a[--i]+e?s:a[i]+e,e+=c[i]==69);printf("%d",s);}