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.0140507164114134x):
#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<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.4544465182623365x):
#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;

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

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

using namespace std;



#define ll long long

#define dbg(x) cout << #x << " = " << x << endl



int n, w;

vector<int> valor, peso;

int INF = INT_MAX;

vector<vector<ll>> memo;



ll dp(int i, int weight) {

    if (weight < 0) return -INF;

    if (i == n) return 0;

    ll &ans = memo[i][weight];

    if (ans != -1) return ans;

    return ans = max(dp(i + 1, weight), dp(i + 1, weight - peso[i]) + valor[i]);

}



int main() {

    #ifdef LOCAL

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

        // freopen("output.txt", "w", stdout);

    #else

        #define endl '\n'

    #endif

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cin >> n >> w;

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

        int a, b; cin >> a >> b;

        peso.push_back(a);

        valor.push_back(b);

    }

    memo.resize(n + 5, vector<ll>(w + 5, -1));

    cout <<  dp(0, 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.7515936006467558x):
#include <bits/stdc++.h>

using namespace std;



#define ll long long

#define dbg(x) cout << #x << " = " << x << endl



int n, w;

vector<int> valor, peso;

int INF = INT_MAX;

vector<vector<ll>> memo;



ll dp(int i, int weight) {

    if (weight < 0) return -INF;

    if (i == n) return 0;

    ll &ans = memo[i][weight];

    if (ans != -1) return ans;

    return ans = max(dp(i + 1, weight), dp(i + 1, weight - peso[i]) + valor[i]);

}



int main() {

    #ifdef LOCAL

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

        // freopen("output.txt", "w", stdout);

    #else

        #define endl '\n'

    #endif

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cin >> n >> w;

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

        int a, b; cin >> a >> b;

        peso.push_back(a);

        valor.push_back(b);

    }

    memo.resize(n + 5, vector<ll>(w + 5, -1));

    cout <<  dp(0, w) << endl;

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

using namespace std;



#define ll long long

#define dbg(x) cout << #x << " = " << x << endl



int n, w;

vector<int> valor, peso;

int INF = INT_MAX;

vector<vector<ll>> memo;



ll dp(int i, int weight) {

    if (weight < 0) return -INF;

    if (i == n) return 0;

    ll &ans = memo[i][weight];

    if (ans != -1) return ans;

    return ans = max(dp(i + 1, weight), dp(i + 1, weight - peso[i]) + valor[i]);

}



int main() {

    #ifdef LOCAL

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

        // freopen("output.txt", "w", stdout);

    #else

        #define endl '\n'

    #endif

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cin >> n >> w;

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

        int a, b; cin >> a >> b;

        peso.push_back(a);

        valor.push_back(b);

    }

    memo.resize(n + 5, vector<ll>(w + 5, -1));

    cout <<  dp(0, w) << endl;

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

using namespace std;



#define ll long long

#define dbg(x) cout << #x << " = " << x << endl



int n, w;

vector<int> valor, peso;

int INF = INT_MAX;

vector<vector<ll>> memo;



ll dp(int i, int weight) {

    if (weight < 0) return -INF;

    if (i == n) return 0;

    ll &ans = memo[i][weight];

    if (ans != -1) return ans;

    return ans = max(dp(i + 1, weight), dp(i + 1, weight - peso[i]) + valor[i]);

}



int main() {

    #ifdef LOCAL

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

        // freopen("output.txt", "w", stdout);

    #else

        #define endl '\n'

    #endif

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cin >> n >> w;

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

        int a, b; cin >> a >> b;

        peso.push_back(a);

        valor.push_back(b);

    }

    memo.resize(n + 5, vector<ll>(w + 5, -1));

    cout <<  dp(0, 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.5703868383005477x):
#include <bits/stdc++.h>

using namespace std;

 

#define MOD (1000000007)

#define f first

#define s second

#define pb(x) push_back(x)

#define mp(x,y) make_pair(x,y)

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

#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;

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

#define forr(i,a,b) for(int i = (a); i > (b); i--)

#define input(vec,N) for(int i = 0; i < (N); i++) cin >> vec[i];

typedef long long int ll;

#define ld long double

const int N = 2e5+30;

//https://codeforces.com/problemset/page/2?tags=1700-1700

 

 

void solve(){

   int N,W;

   cin>>N>>W;

   int w[N+3];

   int v[N+3];

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

   ll dp[N+3][W+6];

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

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

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

       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';

}

 

 

int main(){

 	ios_base::sync_with_stdio(false);

  cin.tie(NULL);

	int T;

  //cin >> T;

  //cout<<prs.size()<<'\n';

	 T = 1;

  //visited[1]=1;

	while(T--){

		solve();

	}

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

using namespace std;

 

#define MOD (1000000007)

#define f first

#define s second

#define pb(x) push_back(x)

#define mp(x,y) make_pair(x,y)

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

#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;

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

#define forr(i,a,b) for(int i = (a); i > (b); i--)

#define input(vec,N) for(int i = 0; i < (N); i++) cin >> vec[i];

typedef long long int ll;

#define ld long double

const int N = 2e5+30;

//https://codeforces.com/problemset/page/2?tags=1700-1700

 

 

void solve(){

   int N,W;

   cin>>N>>W;

   int w[N+3];

   int v[N+3];

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

   ll dp[N+3][W+6];

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

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

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

       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';

}

 

 

int main(){

 	ios_base::sync_with_stdio(false);

  cin.tie(NULL);

	int T;

  //cin >> T;

  //cout<<prs.size()<<'\n';

	 T = 1;

  //visited[1]=1;

	while(T--){

		solve();

	}

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

using namespace std;

 

#define MOD (1000000007)

#define f first

#define s second

#define pb(x) push_back(x)

#define mp(x,y) make_pair(x,y)

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

#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;

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

#define forr(i,a,b) for(int i = (a); i > (b); i--)

#define input(vec,N) for(int i = 0; i < (N); i++) cin >> vec[i];

typedef long long int ll;

#define ld long double

const int N = 2e5+30;

//https://codeforces.com/problemset/page/2?tags=1700-1700

 

 

void solve(){

   int N,W;

   cin>>N>>W;

   int w[N+3];

   int v[N+3];

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

   ll dp[N+3][W+6];

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

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

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

       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';

}

 

 

int main(){

 	ios_base::sync_with_stdio(false);

  cin.tie(NULL);

	int T;

  //cin >> T;

  //cout<<prs.size()<<'\n';

	 T = 1;

  //visited[1]=1;

	while(T--){

		solve();

	}

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

using namespace std;

 

#define MOD (1000000007)

#define f first

#define s second

#define pb(x) push_back(x)

#define mp(x,y) make_pair(x,y)

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

#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;

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

#define forr(i,a,b) for(int i = (a); i > (b); i--)

#define input(vec,N) for(int i = 0; i < (N); i++) cin >> vec[i];

typedef long long int ll;

#define ld long double

const int N = 2e5+30;

//https://codeforces.com/problemset/page/2?tags=1700-1700

 

 

void solve(){

   int N,W;

   cin>>N>>W;

   int w[N+3];

   int v[N+3];

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

   ll dp[N+3][W+6];

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

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

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

       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';

}

 

 

int main(){

 	ios_base::sync_with_stdio(false);

  cin.tie(NULL);

	int T;

  //cin >> T;

  //cout<<prs.size()<<'\n';

	 T = 1;

  //visited[1]=1;

	while(T--){

		solve();

	}

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

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.7961489054870752x):
#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;

}