stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

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

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

#include<iostream>

#include<vector>

#include<algorithm>

#include<map>



using namespace std;



typedef long long ll;



const int N = 100050;

int OO = 0x3f3f3f3f;



int n, W;

int v[N], w[N];

vector<ll>mem[109];

int cnt = 0;



ll solve(int idx, int wt)

{

	cnt++;

	if (idx == n)

		return 0;

	if (mem[idx][wt] != -1)

		return mem[idx][wt];

	ll op1 = 0;

	if (wt >= w[idx])

		op1 = solve(idx + 1, wt - w[idx]) + v[idx];

	ll op2 = solve(idx + 1, wt);



	mem[idx][wt] = max(op1, op2);



	return mem[idx][wt];

}



int main() {





	cin >> n >> W;

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

	{

		mem[i].resize(W+5);

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

			mem[i][j] = -1;

	}



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

	{

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

	}

	solve(0, W);

	//cout << cnt << endl;

	cout << mem[0][W] << endl;

	/*int mx = 0;

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

		mx = max(mem[i][W], mx);

	cout << mx << endl;*/



	//system("pause");

	return 0;

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

}

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

#include<iostream>

#include<vector>

#include<algorithm>

#include<map>



using namespace std;



typedef long long ll;



const int N = 100050;

int OO = 0x3f3f3f3f;



int n, W;

int v[N], w[N];

vector<ll>mem[109];

int cnt = 0;



ll solve(int idx, int wt)

{

	cnt++;

	if (idx == n)

		return 0;

	if (mem[idx][wt] != -1)

		return mem[idx][wt];

	ll op1 = 0;

	if (wt >= w[idx])

		op1 = solve(idx + 1, wt - w[idx]) + v[idx];

	ll op2 = solve(idx + 1, wt);



	mem[idx][wt] = max(op1, op2);



	return mem[idx][wt];

}



int main() {





	cin >> n >> W;

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

	{

		mem[i].resize(W+5);

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

			mem[i][j] = -1;

	}



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

	{

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

	}

	solve(0, W);

	//cout << cnt << endl;

	cout << mem[0][W] << endl;

	/*int mx = 0;

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

		mx = max(mem[i][W], mx);

	cout << mx << endl;*/



	//system("pause");

	return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

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

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

#define endl '\n'

using namespace std;

typedef long long ll;

const int c=1e5;

const ll mod=1e9+7;

/*bool p[1000];

void sieve(){

p[0]=p[1]=1;

for(int i=2;i<=100;i++){

    for(int j=i*i;j<=100;j+=i){

        p[j]=1;

    }

}

}*/

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    int n,s;



    cin>>n>>s;

    ll w[n+5],v[n+5];

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

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

        //p[i]={w,v};

    }

ll dp[n+5][s+5]={},ans=0;



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

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

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

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

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

       dp[i][j]=ans;

    }

}

cout<<dp[n][s];

    return 0;

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

}

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

#define endl '\n'

using namespace std;

typedef long long ll;

const int c=1e5;

const ll mod=1e9+7;

/*bool p[1000];

void sieve(){

p[0]=p[1]=1;

for(int i=2;i<=100;i++){

    for(int j=i*i;j<=100;j+=i){

        p[j]=1;

    }

}

}*/

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    int n,s;



    cin>>n>>s;

    ll w[n+5],v[n+5];

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

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

        //p[i]={w,v};

    }

ll dp[n+5][s+5]={},ans=0;



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

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

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

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

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

       dp[i][j]=ans;

    }

}

cout<<dp[n][s];

    return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

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

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

using namespace std;



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

#define ll long long

#define pb push_back

#define F first

#define S second

#define endl '\n'

#define mod 1e9 + 7

const ll maxN = 1e5+5;

const ll inf = 0x3f3f3f3f;



ll weight[maxN], value[maxN], dp[105][maxN];



int main() {

	Omar45

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

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

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



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

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

            ll opt1 = dp[item-1][rem];

            ll opt2 = 0;

            if (rem>=weight[item])

                opt2 += dp[item-1][rem-weight[item]] + value[item];

            dp[item][rem] = max(opt1, opt2);

        }

    }

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

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

}

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

using namespace std;



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

#define ll long long

#define pb push_back

#define F first

#define S second

#define endl '\n'

#define mod 1e9 + 7

const ll maxN = 1e5+5;

const ll inf = 0x3f3f3f3f;



ll weight[maxN], value[maxN], dp[105][maxN];



int main() {

	Omar45

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

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

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



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

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

            ll opt1 = dp[item-1][rem];

            ll opt2 = 0;

            if (rem>=weight[item])

                opt2 += dp[item-1][rem-weight[item]] + value[item];

            dp[item][rem] = max(opt1, opt2);

        }

    }

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

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

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

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

#define ll long long

using namespace std;



ll dp[100000*100+7];

ll weight[107], value[107];



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);



    int n,w;

    cin>>n>>w;



    /// dp[i]-> maximum total value by taking items with sum of wights exactly i



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

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



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

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

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



    ll ans= 0;



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

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



    cout<< ans <<endl;

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

}

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

#define ll long long

using namespace std;



ll dp[100000*100+7];

ll weight[107], value[107];



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);



    int n,w;

    cin>>n>>w;



    /// dp[i]-> maximum total value by taking items with sum of wights exactly i



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

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



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

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

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



    ll ans= 0;



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

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



    cout<< ans <<endl;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

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

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

#define ull unsigned long long

#define ll long long

#define pb push_back

#define endl '\n'

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

#define mp make_pair

#define mod 1000000007

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

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

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

using namespace std;

const ll  mx=300009;

vector<pair<ll ,ll > > v;

ll  dp[100001];

int main()

{

    ll  n,w;

    cin>>n>>w;

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

    {

        ll  a,b;

        cin>>a>>b;

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

    }

    ll ans=0;

    for(auto x: v)

    {

        for(int used=w-x.first;used>=0;used--)

        {

            dp[used+x.first]=max(dp[used+x.first],dp[used]+x.second);

            ans=max(ans,dp[used+x.first]);

        }

    }

    cout<<ans<<endl;





}

/*

3 5

3 3

4 2

2 4

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

}

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

#define ull unsigned long long

#define ll long long

#define pb push_back

#define endl '\n'

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

#define mp make_pair

#define mod 1000000007

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

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

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

using namespace std;

const ll  mx=300009;

vector<pair<ll ,ll > > v;

ll  dp[100001];

int main()

{

    ll  n,w;

    cin>>n>>w;

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

    {

        ll  a,b;

        cin>>a>>b;

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

    }

    ll ans=0;

    for(auto x: v)

    {

        for(int used=w-x.first;used>=0;used--)

        {

            dp[used+x.first]=max(dp[used+x.first],dp[used]+x.second);

            ans=max(ans,dp[used+x.first]);

        }

    }

    cout<<ans<<endl;





}

/*

3 5

3 3

4 2

2 4

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

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

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

using namespace std;

typedef long long ll;

ll n, w[101], v[101], dp[101][100001], w1;

int main(){

cin >> n >> w1;

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

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

}

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

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

        if(j < w[i]){

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

        }

        else{

            //cout << dp[i - 1][j] << " " << (dp[i - 1][j - w[i]] + v[i]);

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

        }

    }

}

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

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

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

    }

    cout << endl;

}*/

cout << dp[n][w1];

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

}

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

using namespace std;

typedef long long ll;

ll n, w[101], v[101], dp[101][100001], w1;

int main(){

cin >> n >> w1;

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

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

}

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

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

        if(j < w[i]){

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

        }

        else{

            //cout << dp[i - 1][j] << " " << (dp[i - 1][j - w[i]] + v[i]);

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

        }

    }

}

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

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

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

    }

    cout << endl;

}*/

cout << dp[n][w1];

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

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

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

using namespace std;



#define ll long long

#define ii pair <int, int>

#define endl "\n"



int main ()

{

	

	ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    #define int ll



    int n, w;

    cin >> n >> w;



    vector <int> weight(n+1, 0);

    vector <int> value(n+1, 0);



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

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

    }



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

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



    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 (weight[i] <= j){

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

    		}

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

    	}

    }



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

    

	return 0;

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

}

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

using namespace std;



#define ll long long

#define ii pair <int, int>

#define endl "\n"



int main ()

{

	

	ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    #define int ll



    int n, w;

    cin >> n >> w;



    vector <int> weight(n+1, 0);

    vector <int> value(n+1, 0);



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

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

    }



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

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



    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 (weight[i] <= j){

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

    		}

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

    	}

    }



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

    

	return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

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

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

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

}

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

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

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

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

#include <unordered_map>

#include <vector>

#include <stack>

#include <algorithm>

#include <list>

#include <set>

#include <climits>

#include <cmath>

#define lli long long int

using namespace std ;



lli eval(vector<lli> &weight, vector<lli> &val, vector<vector<lli> > &dp, int ind, lli w)

{

	if(ind < 0 && w < 0) return INT_MIN ;

	if(ind < 0) return 0 ;

	if(w < 0) return INT_MIN ; 



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



	dp[ind][w] = INT_MIN ;



	lli dtake = eval(weight,val,dp,ind-1,w) ;

	lli take = eval(weight,val,dp,ind-1,w - weight[ind]) ;



	if(take != INT_MIN) take+= val[ind] ;



	return dp[ind][w] = max(take,dtake) ;



}



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

{

	lli n,w ;

	cin>>n>>w ;



	vector<lli> weight(n),val(n) ;

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

	{

		cin>>weight[i]>>val[i] ;

	}



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

	cout<<eval(weight,val,dp,n-1,w)<<endl ;

	return 0;

}