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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

const int dir[4][2] = { -1,0,1,0,0,-1,0,1 };

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

	memset(f, -1, sizeof(f));

	f[0] = 0;

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

		int w, v;

		scanf("%d%d", &w, &v);

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

	printf("%lld\n", ans);



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

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

using namespace std;

typedef long long ll;

const int maxN = 1e2 + 10;



int n, m;

int w[maxN], v[maxN];

ll dp[maxN][100005];



int main(){

//  freopen("abc.inp", "r", stdin); freopen("abc.out", "w", stdout);

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

  cin >> n >> m;

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

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

  }

  for (int pri = 0; pri <= m; ++pri) {

    dp[1][pri] = (pri >= w[1] ? v[1] : 0);

  }

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

    for (int pri = 0; pri <= m; ++pri) {

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

      if (pri >= w[i]) dp[i][pri] = max(dp[i][pri], dp[i-1][pri-w[i]] + v[i]);

    }

  }

  cout << dp[n][m];

return 0;

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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

            dp[wc+wi]=max(dp[wc+wi],dp[wc]+vi);

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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

using namespace std;

typedef long long ll;

const int maxN = 1e2 + 10;



int n, m;

int w[maxN], v[maxN];

ll dp[maxN][100005];



int main(){

//  freopen("abc.inp", "r", stdin); freopen("abc.out", "w", stdout);

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

  cin >> n >> m;

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

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

  }

  for (int pri = 0; pri <= m; ++pri) {

    dp[1][pri] = (pri >= w[1] ? v[1] : 0);

  }

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

    for (int pri = 0; pri <= m; ++pri) {

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

      if (pri >= w[i]) dp[i][pri] = max(dp[i][pri], dp[i-1][pri-w[i]] + v[i]);

    }

  }

  cout << dp[n][m];

return 0;

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

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

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

		for (int j=t;j>=1;j--)

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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

using namespace std;

typedef long long ll;

const int maxN = 1e2 + 10;



int n, m;

int w[maxN], v[maxN];

ll dp[maxN][100005];



int main(){

//  freopen("abc.inp", "r", stdin); freopen("abc.out", "w", stdout);

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

  cin >> n >> m;

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

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

  }

  for (int pri = 0; pri <= m; ++pri) {

    dp[1][pri] = (pri >= w[1] ? v[1] : 0);

  }

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

    for (int pri = 0; pri <= m; ++pri) {

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

      if (pri >= w[i]) dp[i][pri] = max(dp[i][pri], dp[i-1][pri-w[i]] + v[i]);

    }

  }

  cout << dp[n][m];

return 0;

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

using namespace std;

typedef long long ll;

const ll max_n=1e5+100;

const ll inf=0x3f3f3f3f;

ll t,n,m,p[max_n],v[max_n],q[max_n],dp[max_n];

int main(){

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

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    while(cin>>n>>m){

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

            cin>>p[i]>>q[i];

        }

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

        ll ans=0;

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

            for(int j=m;j>=p[i];j--){

                dp[j]=max(dp[j],dp[j-p[i]]+q[i]);

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

            }

        }cout<<ans<<endl;

    }

    return 0;

}


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

using namespace std;

typedef long long ll;

const int maxN = 1e2 + 10;



int n, m;

int w[maxN], v[maxN];

ll dp[maxN][100005];



int main(){

//  freopen("abc.inp", "r", stdin); freopen("abc.out", "w", stdout);

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

  cin >> n >> m;

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

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

  }

  for (int pri = 0; pri <= m; ++pri) {

    dp[1][pri] = (pri >= w[1] ? v[1] : 0);

  }

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

    for (int pri = 0; pri <= m; ++pri) {

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

      if (pri >= w[i]) dp[i][pri] = max(dp[i][pri], dp[i-1][pri-w[i]] + v[i]);

    }

  }

  cout << dp[n][m];

return 0;

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

using namespace std;



typedef long long ll;



const int maxn = 105, maxw = 1e5 + 5;



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

{

    ll n, W, w[maxn], v[maxn], dp[maxw] = {0};

    cin >> n >> W;

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

        scanf("%lld %lld", &w[i], &v[i]);



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

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

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

    

    cout << dp[W] << endl;

    return 0;

}

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

using namespace std;

typedef long long ll;

const int maxN = 1e2 + 10;



int n, m;

int w[maxN], v[maxN];

ll dp[maxN][100005];



int main(){

//  freopen("abc.inp", "r", stdin); freopen("abc.out", "w", stdout);

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

  cin >> n >> m;

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

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

  }

  for (int pri = 0; pri <= m; ++pri) {

    dp[1][pri] = (pri >= w[1] ? v[1] : 0);

  }

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

    for (int pri = 0; pri <= m; ++pri) {

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

      if (pri >= w[i]) dp[i][pri] = max(dp[i][pri], dp[i-1][pri-w[i]] + v[i]);

    }

  }

  cout << dp[n][m];

return 0;

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

const int dir[4][2] = { -1,0,1,0,0,-1,0,1 };

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

	memset(f, -1, sizeof(f));

	f[0] = 0;

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

		int w, v;

		scanf("%d%d", &w, &v);

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

	printf("%lld\n", ans);



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

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

using namespace std;

#define ll long long int



int main() {

    ll n, m, w, v, dp[200000], ans(0);

    cin >> n >> m;

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

        cin >> w >> v;

        for (ll j = m; j >= w; j--) {

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

        }

    }

    for (ll i = 0; i <= m; i++) ans = max(ans, dp[i]);

    cout << ans << endl;

    return 0;

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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

            dp[wc+wi]=max(dp[wc+wi],dp[wc]+vi);

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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

using namespace std;

#define ll long long int



int main() {

    ll n, m, w, v, dp[200000], ans(0);

    cin >> n >> m;

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

        cin >> w >> v;

        for (ll j = m; j >= w; j--) {

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

        }

    }

    for (ll i = 0; i <= m; i++) ans = max(ans, dp[i]);

    cout << ans << endl;

    return 0;

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

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

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

		for (int j=t;j>=1;j--)

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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

using namespace std;

#define ll long long int



int main() {

    ll n, m, w, v, dp[200000], ans(0);

    cin >> n >> m;

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

        cin >> w >> v;

        for (ll j = m; j >= w; j--) {

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

        }

    }

    for (ll i = 0; i <= m; i++) ans = max(ans, dp[i]);

    cout << ans << endl;

    return 0;

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

using namespace std;

typedef long long ll;

const ll max_n=1e5+100;

const ll inf=0x3f3f3f3f;

ll t,n,m,p[max_n],v[max_n],q[max_n],dp[max_n];

int main(){

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

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    while(cin>>n>>m){

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

            cin>>p[i]>>q[i];

        }

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

        ll ans=0;

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

            for(int j=m;j>=p[i];j--){

                dp[j]=max(dp[j],dp[j-p[i]]+q[i]);

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

            }

        }cout<<ans<<endl;

    }

    return 0;

}


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

using namespace std;

#define ll long long int



int main() {

    ll n, m, w, v, dp[200000], ans(0);

    cin >> n >> m;

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

        cin >> w >> v;

        for (ll j = m; j >= w; j--) {

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

        }

    }

    for (ll i = 0; i <= m; i++) ans = max(ans, dp[i]);

    cout << ans << endl;

    return 0;

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

using namespace std;



typedef long long ll;



const int maxn = 105, maxw = 1e5 + 5;



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

{

    ll n, W, w[maxn], v[maxn], dp[maxw] = {0};

    cin >> n >> W;

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

        scanf("%lld %lld", &w[i], &v[i]);



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

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

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

    

    cout << dp[W] << endl;

    return 0;

}

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

using namespace std;

#define ll long long int



int main() {

    ll n, m, w, v, dp[200000], ans(0);

    cin >> n >> m;

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

        cin >> w >> v;

        for (ll j = m; j >= w; j--) {

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

        }

    }

    for (ll i = 0; i <= m; i++) ans = max(ans, dp[i]);

    cout << ans << endl;

    return 0;

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

const int dir[4][2] = { -1,0,1,0,0,-1,0,1 };

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

	memset(f, -1, sizeof(f));

	f[0] = 0;

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

		int w, v;

		scanf("%d%d", &w, &v);

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

	printf("%lld\n", ans);



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

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

#define ll          long long int

#define ld          long double

#define pb          push_back

#define mp          make_pair

#define ff          first

#define se          second

#define scan(n)     scanf("%lld", &n);

#define print(n)    printf("%lld\n", n);

#define fd(n)       fixed<<setprecision(n)

#define MAX         1000000000000000000

#define MAXN        100005

#define LOG         19

#define mod         1000000007

using namespace std;

// good approach

// yes



// ll fun(ll n,ll w){

//     if(n<0){

//         return 0;

//     }

//     if(w>=we[n]){

//         return max(val[n]+fun(n-1,w-we[n]),fun(n-1,w));

//     }

//     else{

//         return fun(n-1,w);

//     }

// }



int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    ll n,w,i,j;

    cin>>n>>w;

    ll we[n+1],val[n+1];

    we[0]=0;

    val[0]=0;

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

        cin>>we[i]>>val[i];

    }

    // cout<<fun(n-1,w);

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

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

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

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

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

                dp[i][j]=max(val[i]+dp[i-1][j-we[i]],dp[i-1][j]);

            }

            else{

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

            }

        }

    }

    cout<<dp[n][w];

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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

            dp[wc+wi]=max(dp[wc+wi],dp[wc]+vi);

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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

#define ll          long long int

#define ld          long double

#define pb          push_back

#define mp          make_pair

#define ff          first

#define se          second

#define scan(n)     scanf("%lld", &n);

#define print(n)    printf("%lld\n", n);

#define fd(n)       fixed<<setprecision(n)

#define MAX         1000000000000000000

#define MAXN        100005

#define LOG         19

#define mod         1000000007

using namespace std;

// good approach

// yes



// ll fun(ll n,ll w){

//     if(n<0){

//         return 0;

//     }

//     if(w>=we[n]){

//         return max(val[n]+fun(n-1,w-we[n]),fun(n-1,w));

//     }

//     else{

//         return fun(n-1,w);

//     }

// }



int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    ll n,w,i,j;

    cin>>n>>w;

    ll we[n+1],val[n+1];

    we[0]=0;

    val[0]=0;

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

        cin>>we[i]>>val[i];

    }

    // cout<<fun(n-1,w);

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

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

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

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

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

                dp[i][j]=max(val[i]+dp[i-1][j-we[i]],dp[i-1][j]);

            }

            else{

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

            }

        }

    }

    cout<<dp[n][w];

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

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

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

		for (int j=t;j>=1;j--)

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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

#define ll          long long int

#define ld          long double

#define pb          push_back

#define mp          make_pair

#define ff          first

#define se          second

#define scan(n)     scanf("%lld", &n);

#define print(n)    printf("%lld\n", n);

#define fd(n)       fixed<<setprecision(n)

#define MAX         1000000000000000000

#define MAXN        100005

#define LOG         19

#define mod         1000000007

using namespace std;

// good approach

// yes



// ll fun(ll n,ll w){

//     if(n<0){

//         return 0;

//     }

//     if(w>=we[n]){

//         return max(val[n]+fun(n-1,w-we[n]),fun(n-1,w));

//     }

//     else{

//         return fun(n-1,w);

//     }

// }



int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    ll n,w,i,j;

    cin>>n>>w;

    ll we[n+1],val[n+1];

    we[0]=0;

    val[0]=0;

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

        cin>>we[i]>>val[i];

    }

    // cout<<fun(n-1,w);

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

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

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

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

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

                dp[i][j]=max(val[i]+dp[i-1][j-we[i]],dp[i-1][j]);

            }

            else{

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

            }

        }

    }

    cout<<dp[n][w];

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

using namespace std;

typedef long long ll;

const ll max_n=1e5+100;

const ll inf=0x3f3f3f3f;

ll t,n,m,p[max_n],v[max_n],q[max_n],dp[max_n];

int main(){

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

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    while(cin>>n>>m){

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

            cin>>p[i]>>q[i];

        }

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

        ll ans=0;

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

            for(int j=m;j>=p[i];j--){

                dp[j]=max(dp[j],dp[j-p[i]]+q[i]);

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

            }

        }cout<<ans<<endl;

    }

    return 0;

}


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

#define ll          long long int

#define ld          long double

#define pb          push_back

#define mp          make_pair

#define ff          first

#define se          second

#define scan(n)     scanf("%lld", &n);

#define print(n)    printf("%lld\n", n);

#define fd(n)       fixed<<setprecision(n)

#define MAX         1000000000000000000

#define MAXN        100005

#define LOG         19

#define mod         1000000007

using namespace std;

// good approach

// yes



// ll fun(ll n,ll w){

//     if(n<0){

//         return 0;

//     }

//     if(w>=we[n]){

//         return max(val[n]+fun(n-1,w-we[n]),fun(n-1,w));

//     }

//     else{

//         return fun(n-1,w);

//     }

// }



int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    ll n,w,i,j;

    cin>>n>>w;

    ll we[n+1],val[n+1];

    we[0]=0;

    val[0]=0;

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

        cin>>we[i]>>val[i];

    }

    // cout<<fun(n-1,w);

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

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

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

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

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

                dp[i][j]=max(val[i]+dp[i-1][j-we[i]],dp[i-1][j]);

            }

            else{

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

            }

        }

    }

    cout<<dp[n][w];

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

using namespace std;



typedef long long ll;



const int maxn = 105, maxw = 1e5 + 5;



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

{

    ll n, W, w[maxn], v[maxn], dp[maxw] = {0};

    cin >> n >> W;

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

        scanf("%lld %lld", &w[i], &v[i]);



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

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

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

    

    cout << dp[W] << endl;

    return 0;

}

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

#define ll          long long int

#define ld          long double

#define pb          push_back

#define mp          make_pair

#define ff          first

#define se          second

#define scan(n)     scanf("%lld", &n);

#define print(n)    printf("%lld\n", n);

#define fd(n)       fixed<<setprecision(n)

#define MAX         1000000000000000000

#define MAXN        100005

#define LOG         19

#define mod         1000000007

using namespace std;

// good approach

// yes



// ll fun(ll n,ll w){

//     if(n<0){

//         return 0;

//     }

//     if(w>=we[n]){

//         return max(val[n]+fun(n-1,w-we[n]),fun(n-1,w));

//     }

//     else{

//         return fun(n-1,w);

//     }

// }



int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    ll n,w,i,j;

    cin>>n>>w;

    ll we[n+1],val[n+1];

    we[0]=0;

    val[0]=0;

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

        cin>>we[i]>>val[i];

    }

    // cout<<fun(n-1,w);

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

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

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

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

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

                dp[i][j]=max(val[i]+dp[i-1][j-we[i]],dp[i-1][j]);

            }

            else{

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

            }

        }

    }

    cout<<dp[n][w];

}