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

using namespace std;

#define db(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<'\n'

const int N = 1e6;

#define ll long long



int main(){

	ios_base::sync_with_stdio(0);

	int a,b,n,W,T,cas=0;

	cin>>n>>W;

	vector<ll> dp(W+1);

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

		int weight, val;

		cin>>weight>>val;

		for(int weight_already=W-weight;weight_already>=0;--weight_already) {

			dp[weight_already+weight] = max(dp[weight_already+weight], dp[weight_already]+val);

		}

	}

	cout<<dp[W]<<endl;

	return 0;

}

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



using namespace std;

#define MAX(a,b) (a>b?a:b)

int main(){

  int num, cap;

  scanf("%d %d", &num,&cap);

  int itens[num+1][2];

  for (size_t i = 1; i < num+1; i++) {

      scanf("%d %d",itens[i],itens[i]+1);

    // printf("%d %d\n",itens[i][0],itens[i][1]);

  }

  num++,cap++;

  long long parciais[num][cap];

  for (size_t i = 0; i < cap; i++) {

    parciais[0][i] = 0;

  }

  for (size_t i = 1; i < num; i++) {

    for (size_t j = 0; j < cap; j++) {

      if(j < itens[i][0])

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

      else

        parciais[i][j] = MAX(parciais[i-1][j],(long long)itens[i][1] + parciais[i-1][j-itens[i][0]]);

    }

  }

  // printf("   ");

  // for (size_t i = 0; i < num; i++) {

  //   printf("qtd%d            ", i);

  // }

  // printf("\n");

  // printf("\n");

  // for (size_t i = 0; i < cap; i++) {

  //   printf("%d  ", i);

  //   for (size_t j = 0; j < num; j++) {

  //     printf("%02lld              ", parciais[j][i]);

  //   }

  //   printf("\n\n");

  // }



  num--,cap--;

  printf("%lld\n",parciais[num][cap]);

}


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

using namespace std;

long long dp[100005];

int main(){

    memset(dp, -1, sizeof(dp));

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

            if(dp[j] == -1) continue;

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

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

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

}

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

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

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

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

#define forv(i, v) for(int i = 0; i < sz(v); ++i)

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

using namespace std;



typedef long long       ll;

typedef long double     ld;

typedef vector<int>     vi;

typedef vector<double>  vd;

typedef vector< vi >    vii;

typedef vector< vd >    vdd;

typedef vector<string>  vs;





int main()

{

	int n , w;

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

	ll dp[w + 5] = {0};

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

		ll wi, vi;

		scanf("%lld%lld", &wi, &vi);

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

			if (j >= wi)dp[j] = max(dp[j], dp[j - wi] + vi);

		}



	}

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



	return 0;

}


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

using namespace std;

    int n,m,l;

    int a[100005]={},u[100005]={},v[100005]={};

    long long ans;

    long long f[100005]={};

void qs(int l,int r)

{

    int i=l,j=r;

    int x=a[(l+r)/2];

    do

    {

        while (a[i]<x) i++;

        while (a[j]>x) j--;

        if (i<=j)

        {

            swap(a[i],a[j]);

            swap(v[i],v[j]);

            i++;j--;

        }

    }while (i<=j);

    if (l<j) qs(l,j);

    if (i<r) qs(i,r);

}

int main()

{

    cin >> n >> m;



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

        memset(a,0,sizeof(a));

        memset(u,0,sizeof(u));

        memset(v,0,sizeof(v));

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

        {

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

        }

        qs(1,n);

        u[0]=1;

        l=0;

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

        {

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

            {

                if ((u[j]==1)&&(a[i]+j<=m))

                {

                    u[j+a[i]]=1;

                    l=max(l,j+a[i]);

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

                }

            }

        }

        ans=0;

        for (int i=m;i>=0;i--)

            if (f[i]>ans) ans=f[i];

        cout << ans << endl;



}


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

using namespace std;



int main() {

long int n,w;

cin>>n>>w;

long int p[n],wt[n];

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

    cin>>wt[i]>>p[i];

}

long long int 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 if(wt[i-1]<=j){

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

        }

        else{

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

        }

    }

}

cout<<dp[n][w];

	return 0;

}


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

#define REP(x,y,z) for(int x=y;x<=z;x++)

#define MSET(x,y) memset(x,y,sizeof(x))

#define M 105

using namespace std;

int n,m,w[M],v[M];

long long dp[100005];

int main()

{

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

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

    

    MSET(dp, -1);

    dp[0] = 0;

    REP(i,1,n) for (int j=m; j>=w[i]; j--) {

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

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

        }

    }

    printf("%lld\n", *max_element(dp, dp+m+1));

    return 0;

}




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

#define ll long long

using namespace std;



ll w[105], v[105], dp[100005];

ll n,k;



ll solve(ll n, ll k)

{

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

    {

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

        {

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

        }

    }

    return dp[k];

}



int main()

{

    cin>>n>>k;



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

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



    cout<< solve(n,k) <<endl;

}


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

#include <vector>

#include <algorithm>

#include <string>

#include <fstream>

using namespace std;



//#define FILE_INPUT

//#define DEBUG_MODE



int n;

int ww;

long long int memo[101][100001];

int w[100];

long long int v[100];



long long int Search(int num, int weight)

{

	if (memo[num][weight] >= 0) {

		//cout << "Load : " << num << " : " << weight << " : " << memo[num][weight] << endl;

		return memo[num][weight];

	}

	if (num == n - 1) {

		long long int max = 0;

		if (weight + w[num] <= ww) {

			max = v[num];

		}

		memo[num][weight] = max;

		//cout << num << " : " << weight << " : " << max << endl;

		return max;

	}

	long long int max = Search(num + 1, weight);

	if (weight + w[num] <= ww) {

		long long int value2 = v[num] + Search(num + 1, weight + w[num]);

		if (value2 > max) {

			max = value2;

		}

	}

	memo[num][weight] = max;

	//cout << num << " : " << weight << " : " << max << endl;

	return max;

}



int main()

{

#ifdef FILE_INPUT

	ifstream in("test3.txt");

	cin.rdbuf(in.rdbuf());

#endif	/* FILE_INPUT */  

	cin >> n >> ww;

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

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

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

			memo[i][j] = -1;

		}

	}



	long long int max_value = Search(0, 0);

	cout << max_value << endl;



	return 0;

}

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

#include <vector>

#include <algorithm>

#include <string>

#include <fstream>

using namespace std;



//#define FILE_INPUT

//#define DEBUG_MODE



long long int dp[100001];



void DebugPrint(int n, long long int *a)

{

#ifdef DEBUG_MODE

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

		cout << a[i] << ",";

	}

	cout << endl;

#endif

}



int main()

{

#ifdef FILE_INPUT

	ifstream in("test3.txt");

	cin.rdbuf(in.rdbuf());

#endif	/* FILE_INPUT */  



	int n, ww;

	cin >> n >> ww;



	vector<int> w(100);

	vector<int> v(100);

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

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

	}



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

		dp[i] = 0;

	}

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

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

			int j2 = j + w[i];

			if (j2 <= ww) {

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

			}

		}

		DebugPrint(ww + 1, dp);

	}

	cout << dp[ww] << endl;



	return 0;

}

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

using namespace std;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }

template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

typedef long long ll;

typedef vector<int> vint;

typedef pair<int, int> pint;

typedef vector<long long> vlong;

#define _GLIBCXX_DEBUG

#define vpush(a,x) a.push_back(x);

#define rep(i, n) REP(i, 0, n)

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

#define REP(i, x, n) for(int i = x; i < n; i++)

#define INF 2e9

signed main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n,W;

    cin>>n>>W;

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

    vint w(n+1);

    vint v(n+1);

    REP(i,1,n+1){

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

    }

    REP(i,1,n+2){

	rep(j,W+1){

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

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

	    }

	    else{

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

	    }

	}

    }

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

    return(0);

}


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

using namespace std;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }

template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

typedef long long ll;

typedef vector<int> vint;

typedef pair<int, int> pint;

typedef vector<long long> vlong;

#define _GLIBCXX_DEBUG

#define vpush(a,x) a.push_back(x);

#define rep(i, n) REP(i, 0, n)

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

#define REP(i, x, n) for(int i = x; i < n; i++)

#define INF 2e9

signed main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n,W;

    cin>>n>>W;

    vint w(n+1);

    vint v(n+1);

    REP(i,1,n+1){

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

    }

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

    REP(i,1,n+1){

	rep(j,W+1){

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

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

	    }

	    else{

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

	    }

	}

    }

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

    return(0);

}


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

#include <cstring>

#include <vector>

#include <algorithm>

#include <cmath>

#include <string>

#include <set>

#include <utility>

#include <cstdlib>

#include <queue>

#include <stack>

#include <iomanip>

#include <cstdio>

#include <map>



using namespace std;



using ll = long long;

using P = pair<ll,ll>;



#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)

#define rrep(i,x) for(ll i = ((ll)(x) - 1); i >= 0; i--)



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

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

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );



template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}

template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}



//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}

//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}



int dx[4] = {1,0,-1,0};

int dy[4] = {0,1,0,-1};



const ll mod = 1e9 + 7;

const ll IMF = 1e18;

const double PI = 3.14159265358979323846;





// ****************************************CODE***************************************//







ll n,W;

ll w[110],v[110];

ll dp[100010];



int main(){

        cin >> n >> W;

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

        for(int i = 0; i < 100005; i++) dp[i] = -IMF;

        dp[0] = 0;

        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]);

                }

        }



        ll ans = 0;

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

        cout << ans << endl;

        return 0;

}










































































































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

#include <string>

#include <cstring>

#include <vector>

#include <algorithm>

#include <cmath>

#include <set>

#include <utility>

#include <cstdlib>

#include <queue>

#include <stack>

#include <iomanip>

#include <cstdio>

#include <map>

#include <list>

#include <stdio.h>

#include <sstream>

using namespace std;

using ll = long long;

using P = pair<ll,ll>;

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

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}

//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}

const int dx[4] = {1,0,-1,0};

const int dy[4] = {0,1,0,-1};

const ll mod = 1e9 + 7;

const ll inf = 1LL << 60;

const long double pi = 3.14159265358979323846;



// ****************************************CODE***************************************//



ll n, w, weight[110], value[110], dp[110][100100];



int main() {

    cin >> n >> w;

    for(int i = 0; i < n; i++) cin >> weight[i] >> value[i];



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

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

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

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

        }

    }



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

}

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

using namespace std;

using i64 = int64_t;

using vi = vector<i64>;

using vvi = vector<vi>;



i64 dp[101][101010];



int main() {

    int n, W;

    cin >> n >> W;



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

        int v, w;

        cin >> w >> v;

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

            if (j - w >= 0) {

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

            } else {

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

            }

        }

    }

    i64 ans = 0;

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

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

    }

    cout << ans << endl;

}


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

using namespace std;

using i64 = int64_t;

using vi = vector<i64>;

using vvi = vector<vi>;



i64 solve_knapsack_small_weight(const vi &ws, const vi &vs, int MAX_WEIGHT) {

    int n = ws.size();

    vi value(MAX_WEIGHT + 1);

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

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

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

                value[j] = max(value[j], value[j - ws[i]] + vs[i]);

            }

        }

    }

    i64 nax = 0;

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

        nax = max(nax, value[i]);

    }

    return nax;

}



int main() {

    int n, w;

    cin >> n >> w;

    vi ws(n), vs(n);

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

        cin >> ws[i] >> vs[i];

    }

    cout << solve_knapsack_small_weight(ws, vs, w) << endl;

}


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

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

#define rrep(i,m,n) for(int i = m; i >= n; i--)

#define print(x) cout << (x) << endl;

#define print2(x,y) cout << (x) << " " << (y) << endl;

#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;

#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}

#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;

#define INF (1e18)

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

typedef struct{

    ll to;

    ll cost;

} edge;

typedef pair<ll, ll> lpair;

ll dp[110][100010] = {};



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N,W;

    ll w[110], v[110];

    cin >> N >> W;

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

    ll dp[100010] = {};

    rep(i,0,N){

        rrep(j,W, w[i]){

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

        }

    }

    print(dp[W]);

    // ll N,W;

    // ll w[110], v[110];

    // cin >> N >> W;

    // rep(i,0,N){

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

    // }

    // rep(i,0,N){

    //     rep(j,0,W+1){

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

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

    //         }else{

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

    //         }

    //     }

    // }

    // print(dp[N][W]);

}


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

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using lpair = pair<ll, ll>;

const ll MOD = 1e9+7;

const ll INF = 1e18;

#define rep(i,m,n) for(ll i=(m);i<(n);i++)

#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)

#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};

void print() {}

template <class H,class... T>

void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}

ll dp[110][100010] = {};



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N,W;

    cin >> N >> W;

    ll w[110], v[110];

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

    dp[0][0] = 0;

    rep(i,0,N){

        rep(j,0,W+1){

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

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

            }

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

        }

    }

    print(dp[N][W]);





}

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

using namespace std;

#define M 1000000007

#define U 998244353

#define N 1300005

#define int long long

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

#define fr first

#define ll long long 

#define sc second

#define pb push_back

#define mp make_pair

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

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

#define r0 return 0;

#define endl '\n'

#define INF (int)1e15

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1){

    std::cerr << name << " : " << arg1 << endl;

}

template <typename Arg1, typename... Args>

void __f(const char* names, Arg1&& arg1, Args&&... args){

    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);

}

int power(int x, unsigned int y, unsigned int m)

{

    if (y == 0)

        return 1;

    int p = power(x, y/2, m) % m;

    p = (p * p) % m;

    return (y%2 == 0)? p : (x * p) % m;

}

        int dp[100001];

signed main()

{

    ios_base::sync_with_stdio(0);

    int TESTS=1;

    // cin>>TESTS;

    while(TESTS--)

    {   

        int n,w;

        cin>>n>>w;

        pair<int,int> a[n];

        rep(i,0,n){

            int b,c;

            cin>>b>>c;

            a[i] = {b,c};

        }

        dp[0] = 0;

        rep(i,1,100001) dp[i] = -INF;

        rep(i,0,n){

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

                if(dp[j]!=-INF){

                    if(a[i].fr+j>w) continue;

                    dp[a[i].fr+j] = max(dp[a[i].fr+j], dp[j]+a[i].sc);

                }

            }

        }

        int ans=-INF;

        rep(i,0,w+1) ans = max(ans,dp[i]);

        cout<<ans;

    }       

}     

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

using namespace std;

#define M 1000000007

#define U 998244353

#define N 1000005

#define int long long

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

#define fr first

#define ll long long 

#define sc second

#define pb push_back

#define mp make_pair

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

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

#define r0 return 0;

#define endl '\n'

#define INF (int)1e15

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1){

	std::cerr << name << " : " << arg1 << endl;

}

template <typename Arg1, typename... Args>

void __f(const char* names, Arg1&& arg1, Args&&... args){

	const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);

}

signed main()

{

	ios_base::sync_with_stdio(0);

	int TESTS=1;

	// cin>>TESTS;

	while(TESTS--)

	{   

		int n,w;

		cin >> n >> w;

		int val[w+1]={};

		rep(i,0,w+1) val[i] = -1;

		val[0] = 0;

		rep(i,0,n){

			int t;

			cin >> t;

			int r;;

			cin >> r;

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

				if(j+t<=w && val[j]!=-1){

					val[j+t] = max(val[j+t], val[j]+r);

				}

			}

		}

		int mx = -INF;

		rep(j,0,w+1) mx = max(mx, val[j]);

		cout<<mx;

	}

}

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

#include<math.h>

#include<algorithm>



#define long long long



using namespace std;



long n, m;

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



long cal(int idx, int weight) {

    if (idx > n) return 0;

    if (dp[idx][weight] != -1) return dp[idx][weight];

    dp[idx][weight] = 0;



    if (weight + w[idx] <= m) dp[idx][weight] = max(cal(idx + 1, weight), cal(idx + 1, weight + w[idx]) + v[idx]);

    else dp[idx][weight] = dp[idx][weight] = cal(idx + 1, weight);

    return dp[idx][weight];

}



void FastInput()

{

    ios_base::sync_with_stdio(NULL);

    cin.tie(NULL);

    cout.tie(NULL);

}



void Input()

{

    cin >> n >> m;

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

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

        for (int j = 0; j <= 100000; j ++) dp[i][j] = -1;

}



void Solve()

{

    cout << cal(1,0);

}



int main()

{

    FastInput();

    Input();

    Solve();

}




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

#include<algorithm>

#include<math.h>

#include<cstring>

#include<vector>



using namespace std;



#define long long long

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

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



const int MAXN = 1e5 + 5;

const long oo = 1e15;



long ans , n , m;

long dp[MAXN] , w[MAXN] , v[MAXN];



void Solve() {

    ft(i , 1 , n) {

        fd(j , m , w[i]) {

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

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

        }

    }

    cout << ans;

}



void FastInput() {

    ios_base::sync_with_stdio(NULL);

    cin.tie(NULL);

    cout.tie(NULL);

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

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

}



void Input() {

    cin >> n >> m;

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

}



int main() {

    FastInput();

    Input();

    Solve();

}

// Fastest known solution for this problem: