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

using namespace std;



int main() {

    long long n, w;

    cin >> n >> w;

    vector<pair<long long, long long> >v;

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

        long long val, wt;

        cin >> wt >> val;

        v.push_back(make_pair(val, wt));

    }

    sort(v.begin(), v.end());

    long long dp[w + 1];

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

        dp[i] = 0;

    }

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

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

            if(j - v[i].second < 0)

                break;

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

        }

    }

    cout << dp[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<cstring>

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<utility>

#include<queue>

#include<cmath>

#include<functional>

#include<vector>

#define int long long

using namespace std;

int w[105],v[105],f[105][100005];

signed main()

{

	int N,W;

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

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

    for(int i=1;i<=N;i++)f[i][0]=0;

    for(int i=1;i<=N;i++)for(int j=1;j<=W;j++){if(j>=w[i])f[i][j]=max(f[i-1][j-w[i]]+v[i],f[i-1][j]);else f[i][j]=f[i-1][j];}

    printf("%lld",f[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):
#include <iostream>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <iomanip>

#include <string>

#include <set>

#include <vector>

#include <queue>

#include <stack>

#include <map>

using namespace std;

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

#define fore(i, a, n) for (long long i = a; i < n; i++)

#define ford(i, a, n) for (long long i = n - 1; i >= a; i--)

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

#define sl(a) scanf("%lld", &a)

#define sii(a, b) scanf("%d%d", &a, &b)

#define siii(a, b, c) scanf("%d%d%d", &a, &b, &c)

#define sll(a, b) scanf("%lld%lld", &a, &b)

#define slll(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)

#define debug(a) cout << a << endl

#define pr(a) printf("%d ",a)

#define endl '\n'

#define pi acos(-1.0)

#define tr t[root]

#define lson t[root << 1]

#define rson t[root << 1 | 1]

#define IO ios::sync_with_stdio(false), cin.tie(0)

#define ull unsigned long long

const double eps = 1e-8;

inline int sgn(const double &x) { return x < -eps ? -1 : x > eps; }

typedef long long ll;

const int inf=0x3f3f3f3f;

const int MAXN = 1e5 + 10;

int n,W;

ll w[105],v[105];

ll dp[MAXN];

int main()

{

	sii(n,W);

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

	{

		sll(w[i],v[i]);

	}

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

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

	{

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

		

	}

	printf("%lld\n",dp[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 forn(i, n) for (int i = 0; i < int(n); ++i)

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

#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)

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

#define pb push_back

#define eb emplace_back

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

#define F first

#define S second

#define endl '\n'

#define de(x) cout<<#x<<" = "<<(x)<<endl

#define de2(x,y) cout<<#x<<" = "<<(x) <<' '<< #y<<" = "<<y<<endl;



using namespace std;



typedef long long ll;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());



const int N=1e5+5;

ll dp[N];

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

	int N,W;

	cin>>N>>W;

	forn(i,N){

		int w,v;

		cin>>w>>v;

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

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

		}

	}

	cout<<dp[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):
#include<bits/stdc++.h>

#define int long long

#define ll long long

#define ld long double

#define mod ((ll)1e9+7)

#define maxx ((ll)1e6+5)

#define pb push_back

#define ins insert

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

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

#define test ll t; cin>>t; while(t--)

ll exp(ll x,ll y,ll p){ ll res=1; while(y) {if(y%2) res=(res*x%p)%p; x=(x*x)%p; y/=2; } return res;}

ll expo(ll x,ll y){ ll res=1; while(y) {if(y%2) res=(res*x%mod)%mod; x=(x*x)%mod; y/=2; } return res;}

using namespace std;//ok i saw

signed main()

{

    int n,W,i,j,k;

    cin >> n >> W;

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

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

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

    int d[n+1][W+1];

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

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

			d[i][j] = 0;

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

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

		{

			d[i][j] = max(d[i-1][j] , d[i][j-1]);

			if(w[i] <= j)

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

		}

	cout << d[n][W] <<"\n";

    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 <iostream>

#include <algorithm>

#include <map>

#include <set>

#include <vector>

#include <list>

#include <queue>

#include <sstream>

#include <cmath>

#include <functional>

using namespace std;



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

#define reps(s,i,n) for(int i=s;i<n;i++)

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

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

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

#define int64 long long

#define debug cerr << __FILE__ << ":" << __LINE__ << endl;

#define INF 2147483647



struct Init {

    Init() {

        cin.tie(0);

        ios::sync_with_stdio(false);

        cout.precision(20);

        cout << fixed;

    }

} init;



template <typename _Ty>

ostream& operator << (ostream& ostr, const vector<_Ty>& v) {

    for(int i = 0; i < (int) v.size(); i++) {

        ostr << v[i] << (i + 1 != v.size() ? " " : "");

    }

    return ostr;

}



template <typename _K, typename _V>

ostream& operator << (ostream& ostr, const map<_K, _V>& v) {

    ostr << "{";

    for (auto iter = v.begin(); iter != v.end(); ++iter) {

        ostr << (*iter).first << ": " << (*iter).second << ", ";

    }

    ostr << "}";

    return ostr;

}



template <typename _K>

ostream& operator << (ostream& ostr, const set<_K>& v) {

    for (auto iter = v.begin(); iter != v.end(); ++iter) {

        ostr << *iter << (iter != v.end() ? " " : "");

    }

    return ostr;

}



template <typename _K, typename _V>

ostream& operator << (ostream& ostr, const pair<_K, _V>& v) {

    ostr << v.first << " " << v.second;

    return ostr;

}



int nCr(int n, int r) {

    int result = 1;

    rep(i, r) {

        result *= (n - i);

    }

    rep(i, r) {

        result = result / (i + 1);

    }



    return result;

}



int main() {

    int N, W; cin >> N >> W;

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



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

    rep(i, N) {

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

        rep(j, W) {

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

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

            } else {

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

            }

        }

    }



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

}


// 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

int ww[110],v[110];

ll dp[100009];

int main() {

    ios::sync_with_stdio(false);

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

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

    for(int i=1;i<=w;i++)dp[i]=-1e9;

    dp[0]=0;

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

        for(int j=w;j>=ww[i];j--)

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

    cout<<*max_element(dp+1,dp+w+1)<<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>

#define MAX 100005

#define pb push_back

#define mp make_pair

#define pii pair<long long,long long>

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

#define p1(a) cout<<"Check "<<a<<endl;

#define p2(a,b) cout<<"Check "<<a<<' '<<b<<endl;

#define p3(a,b,c) cout<<"Check "<<a<<' '<<b<<' '<<c<<endl;

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

#define ll long long

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

#define MOD 10000000000

#define INF 10000000000000;



using namespace std;



int n,cp;

ll cost[MAX];

int weight[MAX];

ll dp[105][MAX];



ll f(){

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

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

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

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

            }

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

        }

    }

    return dp[n][cp];

}



int main()

{

    cin>>n>>cp;

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

        scanf("%d%lld",&weight[i],&cost[i]);

    }

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

        dp[0][i]=0;

    }

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

        dp[i][0]=0;

    }

    ll ans=f();



    cout<<ans<<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>

#define INF 1073741824

#define ll long long

#define PI (2*acos(0.0))

#define Hare prllf("here\n")

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

#define mp make_pair

#define pb push_back

#define pii pair<ll,ll>

#define x first

#define y second

#define on(val,pos) val|(1<<pos)

#define off(val,pos) val&(~(1<<pos))

#define check(val,pos) (val&(1<<pos))



//first four adjacent,second four corner

//ll row[8]={0,-1,0,1,1,-1,-1,1};

//ll col[8]={-1,0,1,0,-1,-1,1,1};

using namespace std;



int main(){

    ll i,j,k,n,m,val,t=0,cnt,test;

    //freopen("000input.txt","r",stdin);

    cin>>n>>k;

    ll arr[k+5];

    memset(arr,0,sizeof arr);

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

        scanf("%lld %lld",&m,&val);

        for(j=k;j>=m;j--){

            arr[j]=max(arr[j],arr[j-m]+val);

        }

    }

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

    //free();   //if poller array

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

    int n,W;

    cin >> n >> W;

    int w[n+10],v[n+10];

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

        long ww,vv;

        cin >> ww >> vv;

        w[i] = ww;

        v[i] = vv;

    }



    long T[n+1][W+1] = {};

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

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

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

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

            }else{

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

            }

        }

    }



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







}


// 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 n ;

int m ;

long long  dp[100001],v[101],w[101];

int main(){

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

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

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

    }



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

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

        {

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

        }

    }

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

}


// 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 long long long

using namespace std;



const int N = 1e5 + 5;

int n, W;

long w[105], val[105], dp[105][N];



int main(){

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

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

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

    }

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

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

            if(i == 0 || j == 0) dp[i][j] = 0;

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

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

        }

    }

    printf("%lld\n", 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):
/**

     **author : _KMS_

     **created : 29-03-2020

**/

#include<bits/stdc++.h>

using namespace std;

const long long M =1e5+10,MOD=998244353;

typedef long long ll;

ll dp[107][M];

vector<pair<ll,ll>>v;

int main() {

   

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n,w;

  cin>>n>>w;

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

 {

  ll a,b;

  cin>>a>>b;

  v.push_back({a,b});

 }

 sort(v.begin(),v.end());

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

  {



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

    {

      if(v[i-1].first<=j)

      {

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

      }

      else

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

    }

  }

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





  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;



const int MAXW = 1e5 + 10;



long long knapsack[MAXW];

int N,W;



int main(){



	cin >> N >> W;



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

		int w,v;

		cin >> w >> v;

		for(int i = W;i>=w;i--) knapsack[i] = max(knapsack[i-w] + v,knapsack[i]);

	}



	long long best = 0;

	for(int i = 0;i<=W;i++) best = max(best,knapsack[i]);

	cout << best << 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>

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n, w;

ll **mem;

pair<int, ll> *x;

ll nap(int i = 0, int rem = w)

{

    if(i == n)

        return 0;

    if(~mem[i][rem])

        return mem[i][rem];

    ll first = nap(i + 1, rem), second = 0;

    if(rem >= x[i].first)

        second = x[i].second + nap(i + 1, rem - x[i].first);

    return mem[i][rem] = max(first, second);

}

int main()

{

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

    #ifndef ONLINE_JUDGE

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

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

    #endif

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

    mem = new ll*[n];

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

    {

        mem[i] = new ll[w + 1];

        memset(mem[i], -1, (w + 1) * 8);

    }

    x = new pair<int, ll>[n];

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

        scanf("%d %lld", &x[i].first, &x[i].second);

    printf("%lld", nap());

}


// 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 <iostream>

#include <algorithm>



// 0 for Weight index, 1 for Value index

long long arr[101][2];



// The first for Weight, the second for Value

// Notice that all the table is initialized to zero,

// because it's defined in global scope.

// Let's benefit from that.

long long table[100002][101];



int main()

{

	int n, w;

	std::cin >> n >> w;

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

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

	// It sets the initial row.

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

	{

		if (arr[0][0] <= i)

			table[i][0] = arr[0][1];

	}

	// The outer loop for the elements.

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

	{

		// the inner loop for the weight.

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

		{

			if (arr[j][0] > i)

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

			else

				table[i][j] = std::max(table[i][j - 1], static_cast<long long>(arr[j][1]) + table[i - arr[j][0]][j - 1]);

		}

	}

	std::cout << table[w][n - 1] << '\n';

	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: