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

#define ll long long

#define inf 9999999999999999

#define F first

#define S second

#define eb emplace_back

#define mpp make_pair

#define P(x) cout<<__LINE__ <<": "<<#x<<' '<<(x)<<'\n'

#define dbg cout<<__LINE__ <<": 0manush\n"

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

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

#define pi 2*acos(0.0)

#define ee exp(1)

#define mx 100009

#define mod 10000007

using namespace std;

ll dp[109][mx];



int main(){//read(x);

//fast;

ll r,g,h,i,j,t,e,a,b,c,d,n,l,k,z=0;

cin>>n>>k;

ll w[n],p[n];

for(i=0;i<n;i++)cin>>w[i]>>p[i];

dp[n][0]=0;

for(i=1;i<=k;i++)dp[n][i]=inf*-1;

for(i=n-1;i>=0;i--){

    for(j=0;j<=k;j++){

        dp[i][j]=max(dp[i+1][j],(j-w[i]>=0)?p[i]+dp[i+1][j-w[i]]:-inf);

    }

}

l=0;

    for(j=0;j<=k;j++)l=max(l,dp[0][j]);

    cout<<l<<endl;

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

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

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

#define M 105

using namespace std;

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

long long dp[100005];

int main()

{

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

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

    

    MSET(dp, -1);

    dp[0] = 0;

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

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

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

        }

    }

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

    return 0;

}




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

#define ll long long

#define inf 9999999999999999

#define F first

#define S second

#define eb emplace_back

#define mpp make_pair

#define P(x) cout<<__LINE__ <<": "<<#x<<' '<<(x)<<'\n'

#define dbg cout<<__LINE__ <<": 0manush\n"

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

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

#define pi 2*acos(0.0)

#define ee exp(1)

#define mx 100009

#define mod 10000007

using namespace std;

ll dp[109][mx];



int main(){//read(x);

//fast;

ll r,g,h,i,j,t,e,a,b,c,d,n,l,k,z=0;

cin>>n>>k;

ll w[n],p[n];

for(i=0;i<n;i++)cin>>w[i]>>p[i];

dp[n][0]=0;

for(i=1;i<=k;i++)dp[n][i]=inf*-1;

for(i=n-1;i>=0;i--){

    for(j=0;j<=k;j++){

        dp[i][j]=max(dp[i+1][j],(j-w[i]>=0)?p[i]+dp[i+1][j-w[i]]:-inf);

    }

}

l=0;

    for(j=0;j<=k;j++)l=max(l,dp[0][j]);

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



typedef   long long  int ll;

typedef  long double ld;

typedef std::vector<ll> vi;

typedef std::vector<std::vector<ll> > vv;



#define MOD 1000000007

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

#define fo(i,a,b) for(i=a;i<b;i++)

#define mp make_pair

#define pb(x) push_back(x)

#define fi first

#define se second

#define print(vec,a,b) for(ll i=a;i<b;i++) cout<<vec[i]<<" ";cout<<endl;

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

#define input(vec,a,b) for(ll i = a;i<b;i++) cin>>vec[i];

#define ms(a,val) memset(a,val,sizeof(a))

using namespace std;



const int N = 1e5 + 5;





void solve(){

            ll i,j,n,W;

            cin>>n>>W;

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

            fo(i,1,n+1)

            {

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

			}

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

			ms(dp,0);

			fo(i,1,n+1)

			{

				fo(j,1,W+1)

				{

					if(j>=w[i])

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

					else

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

				}

			}

			/*fo(i,1,n+1)

			 {

				 fo(j,1,W+1)

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

				  cout<<endl;

			  }*/

			 //cout<<dp[i][W]<<endl;

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

			

            

						            



















}



int main()

{

    IO;

      ll t=1,i;

      //cin>>t;





      while(t--)

      {



          solve();

      }

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



typedef   long long  int ll;

typedef  long double ld;

typedef std::vector<ll> vi;

typedef std::vector<std::vector<ll> > vv;



#define MOD 1000000007

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

#define fo(i,a,b) for(i=a;i<b;i++)

#define mp make_pair

#define pb(x) push_back(x)

#define fi first

#define se second

#define print(vec,a,b) for(ll i=a;i<b;i++) cout<<vec[i]<<" ";cout<<endl;

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

#define input(vec,a,b) for(ll i = a;i<b;i++) cin>>vec[i];

#define ms(a,val) memset(a,val,sizeof(a))

using namespace std;



const int N = 1e5 + 5;





void solve(){

            ll i,j,n,W;

            cin>>n>>W;

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

            fo(i,1,n+1)

            {

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

			}

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

			ms(dp,0);

			fo(i,1,n+1)

			{

				fo(j,1,W+1)

				{

					if(j>=w[i])

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

					else

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

				}

			}

			/*fo(i,1,n+1)

			 {

				 fo(j,1,W+1)

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

				  cout<<endl;

			  }*/

			 //cout<<dp[i][W]<<endl;

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

			

            

						            



















}



int main()

{

    IO;

      ll t=1,i;

      //cin>>t;





      while(t--)

      {



          solve();

      }

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



typedef   long long  int ll;

typedef  long double ld;

typedef std::vector<ll> vi;

typedef std::vector<std::vector<ll> > vv;



#define MOD 1000000007

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

#define fo(i,a,b) for(i=a;i<b;i++)

#define mp make_pair

#define pb(x) push_back(x)

#define fi first

#define se second

#define print(vec,a,b) for(ll i=a;i<b;i++) cout<<vec[i]<<" ";cout<<endl;

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

#define input(vec,a,b) for(ll i = a;i<b;i++) cin>>vec[i];

#define ms(a,val) memset(a,val,sizeof(a))

using namespace std;



const int N = 1e5 + 5;





void solve(){

            ll i,j,n,W;

            cin>>n>>W;

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

            fo(i,1,n+1)

            {

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

			}

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

			ms(dp,0);

			fo(i,1,n+1)

			{

				fo(j,1,W+1)

				{

					if(j>=w[i])

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

					else

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

				}

			}

			/*fo(i,1,n+1)

			 {

				 fo(j,1,W+1)

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

				  cout<<endl;

			  }*/

			 //cout<<dp[i][W]<<endl;

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

			

            

						            



















}



int main()

{

    IO;

      ll t=1,i;

      //cin>>t;





      while(t--)

      {



          solve();

      }

    return 0;

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

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

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

#define M 105

using namespace std;

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

long long dp[100005];

int main()

{

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

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

    

    MSET(dp, -1);

    dp[0] = 0;

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

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

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

        }

    }

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

    return 0;

}




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



typedef   long long  int ll;

typedef  long double ld;

typedef std::vector<ll> vi;

typedef std::vector<std::vector<ll> > vv;



#define MOD 1000000007

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

#define fo(i,a,b) for(i=a;i<b;i++)

#define mp make_pair

#define pb(x) push_back(x)

#define fi first

#define se second

#define print(vec,a,b) for(ll i=a;i<b;i++) cout<<vec[i]<<" ";cout<<endl;

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

#define input(vec,a,b) for(ll i = a;i<b;i++) cin>>vec[i];

#define ms(a,val) memset(a,val,sizeof(a))

using namespace std;



const int N = 1e5 + 5;





void solve(){

            ll i,j,n,W;

            cin>>n>>W;

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

            fo(i,1,n+1)

            {

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

			}

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

			ms(dp,0);

			fo(i,1,n+1)

			{

				fo(j,1,W+1)

				{

					if(j>=w[i])

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

					else

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

				}

			}

			/*fo(i,1,n+1)

			 {

				 fo(j,1,W+1)

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

				  cout<<endl;

			  }*/

			 //cout<<dp[i][W]<<endl;

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

			

            

						            



















}



int main()

{

    IO;

      ll t=1,i;

      //cin>>t;





      while(t--)

      {



          solve();

      }

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

#define ll long long

using namespace std;



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

ll n,k;



ll solve(ll n, ll k)

{

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

    {

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

        {

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

        }

    }

    return dp[k];

}



int main()

{

    cin>>n>>k;



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

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



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

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

#define ll long long

using namespace std;



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

ll n,k;



ll solve(ll n, ll k)

{

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

    {

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

        {

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

        }

    }

    return dp[k];

}



int main()

{

    cin>>n>>k;



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

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



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

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

#define ll long long

using namespace std;



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

ll n,k;



ll solve(ll n, ll k)

{

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

    {

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

        {

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

        }

    }

    return dp[k];

}



int main()

{

    cin>>n>>k;



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

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



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

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

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

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

#define M 105

using namespace std;

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

long long dp[100005];

int main()

{

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

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

    

    MSET(dp, -1);

    dp[0] = 0;

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

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

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

        }

    }

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

    return 0;

}




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

#define ll long long

using namespace std;



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

ll n,k;



ll solve(ll n, ll k)

{

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

    {

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

        {

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

        }

    }

    return dp[k];

}



int main()

{

    cin>>n>>k;



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

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



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

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

#include <vector>

#include <algorithm>

#include <string>

#include <fstream>

using namespace std;



//#define FILE_INPUT

//#define DEBUG_MODE



int n;

int ww;

long long int memo[101][100001];

int w[100];

long long int v[100];



long long int Search(int num, int weight)

{

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

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

		return memo[num][weight];

	}

	if (num == n - 1) {

		long long int max = 0;

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

			max = v[num];

		}

		memo[num][weight] = max;

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

		return max;

	}

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

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

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

		if (value2 > max) {

			max = value2;

		}

	}

	memo[num][weight] = max;

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

	return max;

}



int main()

{

#ifdef FILE_INPUT

	ifstream in("test3.txt");

	cin.rdbuf(in.rdbuf());

#endif	/* FILE_INPUT */  

	cin >> n >> ww;

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

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

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

			memo[i][j] = -1;

		}

	}



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

	cout << max_value << endl;



	return 0;

}

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

#include <vector>

#include <algorithm>

#include <string>

#include <fstream>

using namespace std;



//#define FILE_INPUT

//#define DEBUG_MODE



long long int dp[100001];



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

{

#ifdef DEBUG_MODE

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

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

	}

	cout << endl;

#endif

}



int main()

{

#ifdef FILE_INPUT

	ifstream in("test3.txt");

	cin.rdbuf(in.rdbuf());

#endif	/* FILE_INPUT */  



	int n, ww;

	cin >> n >> ww;



	vector<int> w(100);

	vector<int> v(100);

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

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

	}



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

		dp[i] = 0;

	}

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

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

			int j2 = j + w[i];

			if (j2 <= ww) {

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

			}

		}

		DebugPrint(ww + 1, dp);

	}

	cout << dp[ww] << endl;



	return 0;

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

using namespace std;

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

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

typedef long long ll;

typedef vector<int> vint;

typedef pair<int, int> pint;

typedef vector<long long> vlong;

#define _GLIBCXX_DEBUG

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

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

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

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

#define INF 2e9

signed main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n,W;

    cin>>n>>W;

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

    vint w(n+1);

    vint v(n+1);

    REP(i,1,n+1){

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

    }

    REP(i,1,n+2){

	rep(j,W+1){

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

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

	    }

	    else{

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

	    }

	}

    }

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

    return(0);

}


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

using namespace std;

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

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

typedef long long ll;

typedef vector<int> vint;

typedef pair<int, int> pint;

typedef vector<long long> vlong;

#define _GLIBCXX_DEBUG

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

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

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

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

#define INF 2e9

signed main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n,W;

    cin>>n>>W;

    vint w(n+1);

    vint v(n+1);

    REP(i,1,n+1){

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

    }

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

    REP(i,1,n+1){

	rep(j,W+1){

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

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

	    }

	    else{

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

	    }

	}

    }

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

    return(0);

}