stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;



}


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

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const long long maxn=100000+50;

long long n,m,w[maxn],v[maxn],dp[maxn];

int main()

{

	cin>>n>>m;

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

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

	{

		for(long long 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.6067322057037985x):
#include<iostream>

using namespace std;



long long dp[110][100010];



int main()

{

	int n,m;

	int v[110], w[110];

	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=1; j<=m ; j++)

		{

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

			if(w[i] <= j)

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

			

		}

	}

	cout << dp[n][m];

}
// 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.7990216704061592x):
#include<iostream>

using namespace std;



long long dp[110][100010];



int main()

{

	int n,m;

	int v[110], w[110];

	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=1; j<=m ; j++)

		{

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

			if(w[i] <= j)

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

			

		}

	}

	cout << dp[n][m];

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



}


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

using namespace std;



long long dp[110][100010];



int main()

{

	int n,m;

	int v[110], w[110];

	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=1; j<=m ; j++)

		{

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

			if(w[i] <= j)

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

			

		}

	}

	cout << dp[n][m];

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

#include <set>

using namespace std;

#define mp             make_pair

#define pb             push_back

#define fi             first

#define se             second

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

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

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

typedef long long      ll;

typedef pair<int, int> ii;

typedef pair<ii, int>  iii;

typedef vector<int>    vi;

typedef vector<ii>     vii;

typedef vector<iii>    viii;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  ll N, W;

  cin >> N >> W;



  ll w[N+1];

  ll v[N+1];



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

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

  }



  ll dp[N+1][W+1];

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

      dp[i][0] = 0;

  }

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

      dp[0][i] = 0;

  }

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

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

          if (w[i] > j) {

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

          } else {

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

          }

      }

  }

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

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

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

    //   }

    //   cout << "\n";

//   }

  cout << dp[N][W] << "\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.7716757511505299x):
#include <bits/stdc++.h>

#include <set>

using namespace std;

#define mp             make_pair

#define pb             push_back

#define fi             first

#define se             second

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

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

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

typedef long long      ll;

typedef pair<int, int> ii;

typedef pair<ii, int>  iii;

typedef vector<int>    vi;

typedef vector<ii>     vii;

typedef vector<iii>    viii;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  ll N, W;

  cin >> N >> W;



  ll w[N+1];

  ll v[N+1];



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

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

  }



  ll dp[N+1][W+1];

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

      dp[i][0] = 0;

  }

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

      dp[0][i] = 0;

  }

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

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

          if (w[i] > j) {

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

          } else {

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

          }

      }

  }

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

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

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

    //   }

    //   cout << "\n";

//   }

  cout << dp[N][W] << "\n";



  return 0;

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



}


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

#include <set>

using namespace std;

#define mp             make_pair

#define pb             push_back

#define fi             first

#define se             second

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

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

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

typedef long long      ll;

typedef pair<int, int> ii;

typedef pair<ii, int>  iii;

typedef vector<int>    vi;

typedef vector<ii>     vii;

typedef vector<iii>    viii;



int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  ll N, W;

  cin >> N >> W;



  ll w[N+1];

  ll v[N+1];



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

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

  }



  ll dp[N+1][W+1];

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

      dp[i][0] = 0;

  }

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

      dp[0][i] = 0;

  }

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

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

          if (w[i] > j) {

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

          } else {

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

          }

      }

  }

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

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

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

    //   }

    //   cout << "\n";

//   }

  cout << dp[N][W] << "\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.607676947468141x):
#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;

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

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



}


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

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

using namespace std;

int  main(){

        long long  n, w; cin>>n>>w;

        long long wt[10000],val[10000];

        for(int i=1;i<=n;i++)cin>>wt[i]>>val[i];

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

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

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

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

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

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

        		

        	}

        }

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

using namespace std;

int  main(){

        long long  n, w; cin>>n>>w;

        long long wt[10000],val[10000];

        for(int i=1;i<=n;i++)cin>>wt[i]>>val[i];

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

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

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

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

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

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

        		

        	}

        }

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

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



}


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

using namespace std;

int  main(){

        long long  n, w; cin>>n>>w;

        long long wt[10000],val[10000];

        for(int i=1;i<=n;i++)cin>>wt[i]>>val[i];

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

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

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

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

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

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

        		

        	}

        }

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

#define MAXN 1e5



using namespace std;



long long dp (long long n, long long W, long long w[], long long v[]){

    long long l[n+1][W+1];



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

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

            if (i==0 or j==0){

                l[i][j]=0;

            }

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

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

            }

            else{

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

            }

        }

    }



    return l[n][W];

}



long long n,m,a,b,c,W;

string s1,s2;



int main(){

    cin>>n>>W;

    long long v[n];

    long long w[n];



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

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

    }

    cout<<dp(n, W, w, v);

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

#define MAXN 1e5



using namespace std;



long long dp (long long n, long long W, long long w[], long long v[]){

    long long l[n+1][W+1];



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

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

            if (i==0 or j==0){

                l[i][j]=0;

            }

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

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

            }

            else{

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

            }

        }

    }



    return l[n][W];

}



long long n,m,a,b,c,W;

string s1,s2;



int main(){

    cin>>n>>W;

    long long v[n];

    long long w[n];



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

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

    }

    cout<<dp(n, W, w, v);

}