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.6393184995841747x):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n,wz,w[110],v[110],dp[100010];

inline int read(){

     int x=0,f=1;char ch=getchar();

     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

     return x*f;

 }

int main ( )

{

	n=read();wz=read();

	for(int i=1;i<=n;i++) w[i]=read(),v[i]=read();

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

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

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

	cout<<dp[wz];

	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.5655741789959423x):
#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define ull unsigned long long

#define mst(a, b) memset((a), (b), sizeof(a))

#define mp(a, b) make_pair(a, b)

#define pi acos(-1)

#define pii pair<int, int>

#define pb push_back

const int INF = 0x3f3f3f3f;

const double eps = 1e-10;

const int maxn = 1e5 + 7;

const int maxm = 5e5 + 10;

ll w[maxn], v[maxn];

ll dp[maxn] = {0};

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    int n, m;

    cin >> n >> m;

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

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

        }

    }

    cout << dp[m] << 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.6070998076081517x):
#include<iostream>

#include<algorithm>

using namespace std;

int v[105],w[105];

long long dp[100005];



int main()

{

	int n,W;

	cin>>n>>W;

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

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

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

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

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

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

	cout<<dp[W];

	//long long ans=-1;

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

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

//	cout<<ans<<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.608024376037209x):
#include <iostream>

using namespace std; 

const int maxn = 1e5+5;

typedef long long ll;

ll n, W, w[maxn], v[maxn], f[maxn];

int main() {

  cin >> n >> W;

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

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

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

      if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];

  cout << f[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.578607075183336x):
#include <iostream>

#include <string>

#include <vector>



struct st{

    int w, v;

};



using namespace std;



void knap(){

    vector<st> structs;

    int n,w;

    cin>>n>>w;

    long maxVal[n+1][w+1];

    structs.push_back({0,0});

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

        int wt, vl;

        cin>> wt >> vl;

        structs.push_back({wt,vl});

    }

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

        maxVal[0][i]=0;

    }

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

        maxVal[i][0]=0;

    }

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

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

            if(j < structs[i].w){

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

            }else{

                maxVal[i][j] = max(maxVal[i-1][j], maxVal[i-1][j-structs[i].w]+ structs[i].v);

            }

        }

    }

    cout<<maxVal[n][w];

}

int main()

{

    knap();

}
// 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: 1.4489720988826584x):
#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);

}
// 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.567175216239643x):
#include<bits/stdc++.h>

using namespace std;

long long dp[2][(int)1e5+9];

main()

{

    ios_base::sync_with_stdio(0);cin.tie(0);

    long long n,w;

    cin >> n >> w;

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

    {

        int x,y;

        cin >> x >> y;

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

        dp[i%2][j]=dp[(i+1)%2][j];

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

        {

        dp[i%2][j]=max(dp[(i+1)%2][j-x]+y,dp[(i+1)%2][j]);

        }

        /*for(int i = 0 ; i < 2 ; ++i)

        {

        cout << endl;

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

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



        }

        cout << endl;*/

    }

    cout << max(dp[n%2][w],dp[(n+1)%2][w]);

}
// 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.7717216350951555x):
#include<bits/stdc++.h>

using namespace std;

long long dp[2][(int)1e5+9];

main()

{

    ios_base::sync_with_stdio(0);cin.tie(0);

    long long n,w;

    cin >> n >> w;

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

    {

        int x,y;

        cin >> x >> y;

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

        dp[i%2][j]=dp[(i+1)%2][j];

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

        {

        dp[i%2][j]=max(dp[(i+1)%2][j-x]+y,dp[(i+1)%2][j]);

        }

        /*for(int i = 0 ; i < 2 ; ++i)

        {

        cout << endl;

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

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



        }

        cout << endl;*/

    }

    cout << max(dp[n%2][w],dp[(n+1)%2][w]);

}
// 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.5698983807780693x):
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;

int n, c, we[105], v[105];

long long mem[105][N];

bool vis[105][N];



long long dp(int idx, int w) {

	if (idx == n || w >= c) {

		return 0;

	}

	if (vis[idx][w]) {

		return mem[idx][w];

	}

	vis[idx][w] = true;



	long long ans = dp(idx + 1, w);

	if (w + we[idx] <= c) {

		ans = max(ans, (long long) v[idx] + dp(idx + 1, w + we[idx]));

	}



	return mem[idx][w] = ans;

}



int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);



	cin >> n >> c;



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

		cin >> we[i] >> v[i];

	}



	cout << dp(0, 0) << '\n';



	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.7736010118895924x):
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;

int n, c, we[105], v[105];

long long mem[105][N];

bool vis[105][N];



long long dp(int idx, int w) {

	if (idx == n || w >= c) {

		return 0;

	}

	if (vis[idx][w]) {

		return mem[idx][w];

	}

	vis[idx][w] = true;



	long long ans = dp(idx + 1, w);

	if (w + we[idx] <= c) {

		ans = max(ans, (long long) v[idx] + dp(idx + 1, w + we[idx]));

	}



	return mem[idx][w] = ans;

}



int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);



	cin >> n >> c;



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

		cin >> we[i] >> v[i];

	}



	cout << dp(0, 0) << '\n';



	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.6257898722198596x):
//		Knapsack

#include<bits/stdc++.h>

using namespace std;

vector<int> v,w;

long long int arr[105][100000];

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

	if(a>b) return a;

	return b;

}

main(){

	//printf("WTF");

	int item,maxW,temp1,temp2;

	scanf("%d %d",&item,&maxW);

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

		scanf("%d %d",&temp1,&temp2);

		w.push_back(temp1);

		v.push_back(temp2);

	}

	/*for(int i=0;i<item;i++){

		scanf("%d",&temp1);

		v.push_back(temp1);

	}

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

		scanf("%d",&temp1);

		w.push_back(temp1);

	}*/

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

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

			

			if(j>=w[i]){

				

				if(i==0) arr[i][j]=v[i];

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

				

			}

			else{

				if(i==0) arr[i][j]=0;

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

			}

		}

	}

	printf("%lld",arr[item-1][maxW]);

}

/*

10 165

92

   57

   49

   68

   60

   43

   67

   84

   87

   72

   23

   31

   29

   44

   53

   38

   63

   85

   89

   82

*/

/*

24 6404180

825594

1677009

1676628

1523970

943972

97426

69666

1296457

1679693

1902996

1844992

1049289

1252836

1319836

953277

2067538

675367

853655

1826027

65731

901489

577243

466257

369261

382745

799601

909247

729069

467902

44328

34610

698150

823460

903959

853665

551830

610856

670702

488960

951111

323046

446298

931161

31385

496951

264724

224916

169684

*/
// 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.8121742124949662x):
//		Knapsack

#include<bits/stdc++.h>

using namespace std;

vector<int> v,w;

long long int arr[105][100000];

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

	if(a>b) return a;

	return b;

}

main(){

	//printf("WTF");

	int item,maxW,temp1,temp2;

	scanf("%d %d",&item,&maxW);

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

		scanf("%d %d",&temp1,&temp2);

		w.push_back(temp1);

		v.push_back(temp2);

	}

	/*for(int i=0;i<item;i++){

		scanf("%d",&temp1);

		v.push_back(temp1);

	}

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

		scanf("%d",&temp1);

		w.push_back(temp1);

	}*/

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

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

			

			if(j>=w[i]){

				

				if(i==0) arr[i][j]=v[i];

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

				

			}

			else{

				if(i==0) arr[i][j]=0;

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

			}

		}

	}

	printf("%lld",arr[item-1][maxW]);

}

/*

10 165

92

   57

   49

   68

   60

   43

   67

   84

   87

   72

   23

   31

   29

   44

   53

   38

   63

   85

   89

   82

*/

/*

24 6404180

825594

1677009

1676628

1523970

943972

97426

69666

1296457

1679693

1902996

1844992

1049289

1252836

1319836

953277

2067538

675367

853655

1826027

65731

901489

577243

466257

369261

382745

799601

909247

729069

467902

44328

34610

698150

823460

903959

853665

551830

610856

670702

488960

951111

323046

446298

931161

31385

496951

264724

224916

169684

*/
// 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.5950248789473362x):
/******

author :- Mahmoud Tarek.

*******/



#include<bits/stdc++.h>



using namespace std ;



#define rg register

#define dbg(v) cerr << #v << " " << v ;

typedef long long ll ;



int n, w ;

vector<pair<int, int>> a ;

const int N = 1e5 + 5 ;

ll dp[101][N] ;



int main() {

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



    cin >> n >> w ;

    a.resize(n) ;

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

        cin >> a[i].first >> a[i].second ;

    }



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

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

            if(j >= a[i - 1].first){

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

            } else {

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

            }

        }

    }



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











}





/*

  Empty set of troubles.

*/
// 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.7909419242430065x):
/******

author :- Mahmoud Tarek.

*******/



#include<bits/stdc++.h>



using namespace std ;



#define rg register

#define dbg(v) cerr << #v << " " << v ;

typedef long long ll ;



int n, w ;

vector<pair<int, int>> a ;

const int N = 1e5 + 5 ;

ll dp[101][N] ;



int main() {

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



    cin >> n >> w ;

    a.resize(n) ;

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

        cin >> a[i].first >> a[i].second ;

    }



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

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

            if(j >= a[i - 1].first){

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

            } else {

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

            }

        }

    }



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











}





/*

  Empty set of troubles.

*/
// 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.5617355993341113x):
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

#include<unordered_map>

using namespace std;

//<DEFINE>

void Fast() {

	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

}

void File() {

#ifndef ONLINE_JUDGE

	freopen("Input.txt", "r", stdin);

	freopen("Output.txt", "w", stdout);

#endif

}

#define ll long long

#define ull unsigned long long

#define mod 1000000007

ll gcd(ll a, ll b) {

	return!b ? a : gcd(b, a % b);

}

#define fix(n) cout << fixed << setprecision(n);

#define numOfOnes(n) __builtin_popcount(n)

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

#define skip continue

#define stop(n) return cout<<n,0

#define pi  acos(-1)

#define endl "\n"

#define ceil(x,y) (x+y-1)/y

//</DEFINE>



/*█▀▀▄░░░░░░░░░░░▄▀▀█

░█░░░▀▄░▄▄▄▄▄░▄▀░░░█

░░▀▄░░░▀░░░░░▀░░░▄▀

░░░░▌░▄▄░░░▄▄░▐▀▀

░░░▐░░█▄░░░▄█░░▌▄▄▀▀▀▀█

░░░▌▄▄▀▀░▄░▀▀▄▄▐░░░░░░█

▄▀▀▐▀▀░▄▄▄▄▄░▀▀▌▄▄▄░░░█

█░░░▀▄░█░░░█░▄▀░░░░█▀▀▀

░▀▄░░▀░░▀▀▀░░▀░░░▄█▀

░░░█░░░░░░░░░░░▄▀▄░▀▄

░░░█░░░░░░░░░▄▀█░░█░░█

░░░█░░░░░░░░░░░█▄█░░▄▀

░░░█░░░░░░░░░░░████▀

░░░▀█▄▄▄▀▀▀▀▄▄▄█▀*/

int n, w;

vector<pair<int,int>>v;

ll res[101][100001];

//<FUNCTIONS>

ll solve(int idx = 0, int wight = 0) {

	if (idx == n)return 0;

	if (~res[idx][wight])return res[idx][wight];

	ll take = 0, leave;

	if (wight + v[idx].first <= w)take = solve(idx + 1, wight + v[idx].first) + v[idx].second;

	leave = solve(idx + 1, wight);

	return res[idx][wight] = max(leave, take);

}

//</FUNCTIONS>		

int main() {

	Fast();

	cin >> n >> w;

	v.resize(n);

	for (int i = 0; i < n; i++)cin >> v[i].first>> v[i].second;

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

		for (int j = 0; j <= w; j++)res[i][j] = -1;

	}

	cout << solve() << 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.767967513873825x):
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

#include<unordered_map>

using namespace std;

//<DEFINE>

void Fast() {

	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

}

void File() {

#ifndef ONLINE_JUDGE

	freopen("Input.txt", "r", stdin);

	freopen("Output.txt", "w", stdout);

#endif

}

#define ll long long

#define ull unsigned long long

#define mod 1000000007

ll gcd(ll a, ll b) {

	return!b ? a : gcd(b, a % b);

}

#define fix(n) cout << fixed << setprecision(n);

#define numOfOnes(n) __builtin_popcount(n)

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

#define skip continue

#define stop(n) return cout<<n,0

#define pi  acos(-1)

#define endl "\n"

#define ceil(x,y) (x+y-1)/y

//</DEFINE>



/*█▀▀▄░░░░░░░░░░░▄▀▀█

░█░░░▀▄░▄▄▄▄▄░▄▀░░░█

░░▀▄░░░▀░░░░░▀░░░▄▀

░░░░▌░▄▄░░░▄▄░▐▀▀

░░░▐░░█▄░░░▄█░░▌▄▄▀▀▀▀█

░░░▌▄▄▀▀░▄░▀▀▄▄▐░░░░░░█

▄▀▀▐▀▀░▄▄▄▄▄░▀▀▌▄▄▄░░░█

█░░░▀▄░█░░░█░▄▀░░░░█▀▀▀

░▀▄░░▀░░▀▀▀░░▀░░░▄█▀

░░░█░░░░░░░░░░░▄▀▄░▀▄

░░░█░░░░░░░░░▄▀█░░█░░█

░░░█░░░░░░░░░░░█▄█░░▄▀

░░░█░░░░░░░░░░░████▀

░░░▀█▄▄▄▀▀▀▀▄▄▄█▀*/

int n, w;

vector<pair<int,int>>v;

ll res[101][100001];

//<FUNCTIONS>

ll solve(int idx = 0, int wight = 0) {

	if (idx == n)return 0;

	if (~res[idx][wight])return res[idx][wight];

	ll take = 0, leave;

	if (wight + v[idx].first <= w)take = solve(idx + 1, wight + v[idx].first) + v[idx].second;

	leave = solve(idx + 1, wight);

	return res[idx][wight] = max(leave, take);

}

//</FUNCTIONS>		

int main() {

	Fast();

	cin >> n >> w;

	v.resize(n);

	for (int i = 0; i < n; i++)cin >> v[i].first>> v[i].second;

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

		for (int j = 0; j <= w; j++)res[i][j] = -1;

	}

	cout << solve() << endl;

}