stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

            dp[wc+wi]=max(dp[wc+wi],dp[wc]+vi);

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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

using namespace std;



typedef long long ll;

typedef vector<int> vi;



#define PB push_back

#define MP make_pair

#define endl '\n'

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

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

ll n,w[105],v[105], dp[100][100005],limit;



ll f(int pos,int weight)

{

    if(pos== n)   return 0;

    if(dp[pos][weight]> 0)

        return dp[pos][weight];

    ll x=0,y=0;

    if(weight>=w[pos])

        x=v[pos]+f(pos+1,weight-w[pos]);

    y=f(pos+1,weight);

    return dp[pos][weight]=max(x,y);





}



int main()

{

    optimize();

    cin>>n>>limit;

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

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

    ll x=f(0,limit);

    cout<<x;

    return 0;

}
// Slower C++ solution:
#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;

}


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

using namespace std;



typedef long long ll;

typedef vector<int> vi;



#define PB push_back

#define MP make_pair

#define endl '\n'

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

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

ll n,w[105],v[105], dp[100][100005],limit;



ll f(int pos,int weight)

{

    if(pos== n)   return 0;

    if(dp[pos][weight]> 0)

        return dp[pos][weight];

    ll x=0,y=0;

    if(weight>=w[pos])

        x=v[pos]+f(pos+1,weight-w[pos]);

    y=f(pos+1,weight);

    return dp[pos][weight]=max(x,y);





}



int main()

{

    optimize();

    cin>>n>>limit;

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

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

    ll x=f(0,limit);

    cout<<x;

    return 0;

}
// Slower C++ solution:
#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;

}


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

using namespace std;



typedef long long ll;

typedef vector<int> vi;



#define PB push_back

#define MP make_pair

#define endl '\n'

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

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

ll n,w[105],v[105], dp[100][100005],limit;



ll f(int pos,int weight)

{

    if(pos== n)   return 0;

    if(dp[pos][weight]> 0)

        return dp[pos][weight];

    ll x=0,y=0;

    if(weight>=w[pos])

        x=v[pos]+f(pos+1,weight-w[pos]);

    y=f(pos+1,weight);

    return dp[pos][weight]=max(x,y);





}



int main()

{

    optimize();

    cin>>n>>limit;

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

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

    ll x=f(0,limit);

    cout<<x;

    return 0;

}
// Slower C++ solution:
#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;

}

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

using namespace std;



typedef long long ll;

typedef vector<int> vi;



#define PB push_back

#define MP make_pair

#define endl '\n'

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

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

ll n,w[105],v[105], dp[100][100005],limit;



ll f(int pos,int weight)

{

    if(pos== n)   return 0;

    if(dp[pos][weight]> 0)

        return dp[pos][weight];

    ll x=0,y=0;

    if(weight>=w[pos])

        x=v[pos]+f(pos+1,weight-w[pos]);

    y=f(pos+1,weight);

    return dp[pos][weight]=max(x,y);





}



int main()

{

    optimize();

    cin>>n>>limit;

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

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

    ll x=f(0,limit);

    cout<<x;

    return 0;

}
// Slower C++ solution:
#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;

}

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

using namespace std;



typedef long long ll;

typedef vector<int> vi;



#define PB push_back

#define MP make_pair

#define endl '\n'

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

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

ll n,w[105],v[105], dp[100][100005],limit;



ll f(int pos,int weight)

{

    if(pos== n)   return 0;

    if(dp[pos][weight]> 0)

        return dp[pos][weight];

    ll x=0,y=0;

    if(weight>=w[pos])

        x=v[pos]+f(pos+1,weight-w[pos]);

    y=f(pos+1,weight);

    return dp[pos][weight]=max(x,y);





}



int main()

{

    optimize();

    cin>>n>>limit;

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

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

    ll x=f(0,limit);

    cout<<x;

    return 0;

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

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

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

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

	f[0] = 0;

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

		int w, v;

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

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

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



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7990443958128086x):
#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';

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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

            dp[wc+wi]=max(dp[wc+wi],dp[wc]+vi);

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.3094447196592456x):
#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';

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.8047251275089433x):
#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';

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.817492516083292x):
#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';

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.8138224055662224x):
#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';

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.8065353016099506x):
#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';

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

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

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

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

	f[0] = 0;

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

		int w, v;

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

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

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



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

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

using namespace std;



int main()

{

    long long n,cap,i,j;

    cin>>n>>cap;

    long long dp[n+1][cap+1],v[n+5],w[n+2];

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

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



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

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

    {

           if(j<w[i])  dp[i][j]=dp[i-1][j];

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

    }

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

       return 0;

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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

            dp[wc+wi]=max(dp[wc+wi],dp[wc]+vi);

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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

using namespace std;



int main()

{

    long long n,cap,i,j;

    cin>>n>>cap;

    long long dp[n+1][cap+1],v[n+5],w[n+2];

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

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



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

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

    {

           if(j<w[i])  dp[i][j]=dp[i-1][j];

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

    }

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

       return 0;

}
// Slower C++ solution:
#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;

}


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

using namespace std;



int main()

{

    long long n,cap,i,j;

    cin>>n>>cap;

    long long dp[n+1][cap+1],v[n+5],w[n+2];

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

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



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

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

    {

           if(j<w[i])  dp[i][j]=dp[i-1][j];

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

    }

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

       return 0;

}
// Slower C++ solution:
#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;

}


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

using namespace std;



int main()

{

    long long n,cap,i,j;

    cin>>n>>cap;

    long long dp[n+1][cap+1],v[n+5],w[n+2];

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

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



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

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

    {

           if(j<w[i])  dp[i][j]=dp[i-1][j];

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

    }

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

       return 0;

}
// Slower C++ solution:
#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;

}

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

using namespace std;



int main()

{

    long long n,cap,i,j;

    cin>>n>>cap;

    long long dp[n+1][cap+1],v[n+5],w[n+2];

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

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



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

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

    {

           if(j<w[i])  dp[i][j]=dp[i-1][j];

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

    }

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

       return 0;

}
// Slower C++ solution:
#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;

}

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

using namespace std;



int main()

{

    long long n,cap,i,j;

    cin>>n>>cap;

    long long dp[n+1][cap+1],v[n+5],w[n+2];

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

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



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

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

    {

           if(j<w[i])  dp[i][j]=dp[i-1][j];

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

    }

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

       return 0;

}
// Slower C++ solution:
#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;

}




// Faster C++ solution for the same problem (measured speedup: 11.92478499615091x):
#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;

}