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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



ll n, a[maxn], w[maxn], s;

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

		for (int j = s - w; j >= 0; j--) {

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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

#include <vector>

#include <unordered_set>

#include <algorithm>

 

#define ll long long

 

int main(){

	ll w,n;



	std::cin >> n >> w;

	

	std::vector<ll> dp(w+1);

	

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

		ll weight, value;

		std::cin >> weight >> value;

		std::vector<ll> toInsert;

		for(int j = w-weight; j >= 0; j--){

			if(j+weight >= 0 && dp[j] + value > dp[j+weight]){

				dp[j+weight] = dp[j] + value;

			}

		}

	}

	

	ll answer = 0;

	for(int i = 0; i < dp.size(); ++i){

		if(dp[i] > answer)

			answer = dp[i];

	}

	std::cout << answer;

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

using namespace std;

const int maxn = 1e5 + 5;

typedef long long ll;

int main(){

	ll dp[maxn];

	ll n,W;

	ll w[105],v[105];

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

	scanf("%lld%lld",&n,&W);

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

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

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

		for(ll j = W;j >= 1;j--){

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

		}

	}

	printf("%lld\n",dp[W]);

	return 0;

}

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

#include <vector>

#include <unordered_set>

#include <algorithm>

 

#define ll long long

 

int main(){

	ll w,n;



	std::cin >> n >> w;

	

	std::vector<ll> dp(w+1);

	

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

		ll weight, value;

		std::cin >> weight >> value;

		std::vector<ll> toInsert;

		for(int j = w-weight; j >= 0; j--){

			if(j+weight >= 0 && dp[j] + value > dp[j+weight]){

				dp[j+weight] = dp[j] + value;

			}

		}

	}

	

	ll answer = 0;

	for(int i = 0; i < dp.size(); ++i){

		if(dp[i] > answer)

			answer = dp[i];

	}

	std::cout << answer;

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



ll n, a[maxn], w[maxn], s;

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

		for (int j = s - w; j >= 0; j--) {

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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

using namespace std;



#define ll long long

#define pb push_back

#define f first

#define s second

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

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



const int mod = 1e9+7;



//ll binpow(ll a, ll n);

//ll modp(ll a, ll b, int m);

//ll binmul(ll a, ll b, ll c);

long long wp[101], v[101];

long long dp[100001][101];

long long rec(int w, int i){

	

	if (w<0) return INT_MIN;

	else if(i < 1) return 0;

	

	else if(dp[w][i]> 0 ) return dp[w][i];

	

	else{

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

		return dp[w][i];

	}

}

void solve(){

	int w, n; cin>>n>>w;

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

		cin>>wp[i]>>v[i];

	}

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

		dp[0][i] = 0;

	}

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

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

			dp[j][i] = INT_MIN;

		}

	}

	

	cout<<rec(w,n)<<"\n";

}



int main(){

	ios::sync_with_stdio(0);

	cin.tie(0);





	solve();

	return 0;

}



//ll binpow (ll a, ll n) {

//	ll res = 1;

//	while (n) {

//		if (n & 1)

//			res *= a;

//		a *= a;

//		n >>= 1;

//	}

//	return res;

//}



//long long modp(long long a, long long b, int m)

//{

//    int result = 1;

//    while (b > 0)

//    {

//        if (b % 2 == 1)

//            result = (result * a) % m;

//        b = b >> 1;

//        a = (a * a) % m;

//    }

//    return result;

//}



//ll binmul(ll a, ll b, ll c) {

//	if(b == 0) return 0;

//	if(b % 2 == 1) {

//		ll x = binmul(a, b-1, c);

//		return (x+a) % c;

//	}

//	ll x = binmul(a, b/2, c);

//	return x * 2 % c;

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

using namespace std;

const int maxn = 1e5 + 5;

typedef long long ll;

int main(){

	ll dp[maxn];

	ll n,W;

	ll w[105],v[105];

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

	scanf("%lld%lld",&n,&W);

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

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

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

		for(ll j = W;j >= 1;j--){

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

		}

	}

	printf("%lld\n",dp[W]);

	return 0;

}

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

using namespace std;



#define ll long long

#define pb push_back

#define f first

#define s second

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

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



const int mod = 1e9+7;



//ll binpow(ll a, ll n);

//ll modp(ll a, ll b, int m);

//ll binmul(ll a, ll b, ll c);

long long wp[101], v[101];

long long dp[100001][101];

long long rec(int w, int i){

	

	if (w<0) return INT_MIN;

	else if(i < 1) return 0;

	

	else if(dp[w][i]> 0 ) return dp[w][i];

	

	else{

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

		return dp[w][i];

	}

}

void solve(){

	int w, n; cin>>n>>w;

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

		cin>>wp[i]>>v[i];

	}

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

		dp[0][i] = 0;

	}

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

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

			dp[j][i] = INT_MIN;

		}

	}

	

	cout<<rec(w,n)<<"\n";

}



int main(){

	ios::sync_with_stdio(0);

	cin.tie(0);





	solve();

	return 0;

}



//ll binpow (ll a, ll n) {

//	ll res = 1;

//	while (n) {

//		if (n & 1)

//			res *= a;

//		a *= a;

//		n >>= 1;

//	}

//	return res;

//}



//long long modp(long long a, long long b, int m)

//{

//    int result = 1;

//    while (b > 0)

//    {

//        if (b % 2 == 1)

//            result = (result * a) % m;

//        b = b >> 1;

//        a = (a * a) % m;

//    }

//    return result;

//}



//ll binmul(ll a, ll b, ll c) {

//	if(b == 0) return 0;

//	if(b % 2 == 1) {

//		ll x = binmul(a, b-1, c);

//		return (x+a) % c;

//	}

//	ll x = binmul(a, b/2, c);

//	return x * 2 % c;

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



ll n, a[maxn], w[maxn], s;

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

		for (int j = s - w; j >= 0; j--) {

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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

using namespace std;

#define LL long long int

LL dp[101][100001];

int main() {

    ios_base::sync_with_stdio(false);

    LL n,w;

    cin >> n >> w;

    LL wgt[w+1],val[n+1];

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

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

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

            if(wgt[i]>j) dp[i][j] = dp[i-1][j];

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

        }

    }

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

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

using namespace std;

const int maxn = 1e5 + 5;

typedef long long ll;

int main(){

	ll dp[maxn];

	ll n,W;

	ll w[105],v[105];

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

	scanf("%lld%lld",&n,&W);

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

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

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

		for(ll j = W;j >= 1;j--){

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

		}

	}

	printf("%lld\n",dp[W]);

	return 0;

}

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

using namespace std;

#define LL long long int

LL dp[101][100001];

int main() {

    ios_base::sync_with_stdio(false);

    LL n,w;

    cin >> n >> w;

    LL wgt[w+1],val[n+1];

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

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

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

            if(wgt[i]>j) dp[i][j] = dp[i-1][j];

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

        }

    }

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

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



ll n, a[maxn], w[maxn], s;

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

		for (int j = s - w; j >= 0; j--) {

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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

using namespace std;

typedef long long int ll;



ll maxi(ll a, ll b){

    return (a>b)? a : b;

}





int main(){

    ll n, k; cin>> n>> k;

    ll w[n+1]={0}, p[n+1]={0};

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

    ll a[2][k+1];

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

        for(ll j=0; j<=k; j++) a[i][j]=0;

    }

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

        for(ll j=1; j<=k; j++){

            a[1][j]=a[0][j];

            if(j>=w[i] && a[1][j]<a[0][j-w[i]]+p[i]) a[1][j]=a[0][j-w[i]]+p[i];

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

        }

        for(ll j=1; j<=k; j++){

            a[0][j]=a[1][j];

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

        }

        //cout<< endl;

    }

    cout<< a[1][k]<< endl;

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

using namespace std;

const int maxn = 1e5 + 5;

typedef long long ll;

int main(){

	ll dp[maxn];

	ll n,W;

	ll w[105],v[105];

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

	scanf("%lld%lld",&n,&W);

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

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

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

		for(ll j = W;j >= 1;j--){

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

		}

	}

	printf("%lld\n",dp[W]);

	return 0;

}

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

using namespace std;

typedef long long int ll;



ll maxi(ll a, ll b){

    return (a>b)? a : b;

}





int main(){

    ll n, k; cin>> n>> k;

    ll w[n+1]={0}, p[n+1]={0};

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

    ll a[2][k+1];

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

        for(ll j=0; j<=k; j++) a[i][j]=0;

    }

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

        for(ll j=1; j<=k; j++){

            a[1][j]=a[0][j];

            if(j>=w[i] && a[1][j]<a[0][j-w[i]]+p[i]) a[1][j]=a[0][j-w[i]]+p[i];

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

        }

        for(ll j=1; j<=k; j++){

            a[0][j]=a[1][j];

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

        }

        //cout<< endl;

    }

    cout<< a[1][k]<< endl;

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



ll n, a[maxn], w[maxn], s;

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

		for (int j = s - w; j >= 0; j--) {

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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

using namespace std;

using ll = long long;

using PII = pair<int, int>;

using VI = vector<int>;



int main() {

#ifdef LOCAL_EXEC

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

//	freopen("sample.out", "w", stdout);

#else

  ios_base::sync_with_stdio(false); cin.tie(NULL);

#endif



  int n, W; cin >> n >> W;

  vector<ll> dp(W + 1);

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

    int w, v; cin >> w >> v;

    for (int j = W; j >= w; j--) {

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

    }

  }

  cout << dp[W] << endl;



  return 0;

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

using namespace std;

const int maxn = 1e5 + 5;

typedef long long ll;

int main(){

	ll dp[maxn];

	ll n,W;

	ll w[105],v[105];

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

	scanf("%lld%lld",&n,&W);

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

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

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

		for(ll j = W;j >= 1;j--){

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

		}

	}

	printf("%lld\n",dp[W]);

	return 0;

}

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

using namespace std;

using ll = long long;

using PII = pair<int, int>;

using VI = vector<int>;



int main() {

#ifdef LOCAL_EXEC

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

//	freopen("sample.out", "w", stdout);

#else

  ios_base::sync_with_stdio(false); cin.tie(NULL);

#endif



  int n, W; cin >> n >> W;

  vector<ll> dp(W + 1);

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

    int w, v; cin >> w >> v;

    for (int j = W; j >= w; j--) {

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

    }

  }

  cout << dp[W] << endl;



  return 0;

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



ll n, a[maxn], w[maxn], s;

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

		for (int j = s - w; j >= 0; j--) {

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.588039975232676x):
																//  SMOKE SHISHA PLAY FIFA  // 

#include<bits/stdc++.h>

using namespace std;



typedef long long int ll;

typedef long double ld;



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

#define pll pair<ll,ll>

#define mp make_pair

#define ff first

#define ss second

#define pb push_back

#define mod 1000000007

#define lp(start,end) for(ll i=start;i<=end;i++) 

#define deb1(a) cout<<#a<<" = "<<(a)<<endl;

#define deb2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;

#define deb3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;





ll modu(ll a, ll b)

{

	ll ans =1;

	while(b>0)

	{

		if(b&1)

		ans = (ans*a)%mod;

		b/=2;

		a = (a*a)%mod;

	}

	return ans;

}



ll n,w;

ll we[107],v[107];

ll dp[107][100007];



ll fun(ll x, ll curr)

{

	if(dp[x][curr]!=-1)

		return dp[x][curr];

	if(x==n)

	{

		if(curr-we[x] >=0)

			dp[x][curr] = v[x];

		else

			dp[x][curr] = 0; 

	}else {

	if(curr-we[x]>=0)

		dp[x][curr] = max(fun(x+1,curr),fun(x+1,curr-we[x]) + v[x]);

	else

		dp[x][curr] = fun(x+1,curr);

}

//	deb3(x,curr,dp[x][curr]);

	return dp[x][curr];

}



int main()

{

	fastio

	cin >> n >> w;

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

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

	}

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

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

			dp[i][j]=-1;



	cout << fun(1,w) << endl;;

	return 0;	

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

using namespace std;

const int maxn = 1e5 + 5;

typedef long long ll;

int main(){

	ll dp[maxn];

	ll n,W;

	ll w[105],v[105];

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

	scanf("%lld%lld",&n,&W);

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

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

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

		for(ll j = W;j >= 1;j--){

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

		}

	}

	printf("%lld\n",dp[W]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7799415016775864x):
																//  SMOKE SHISHA PLAY FIFA  // 

#include<bits/stdc++.h>

using namespace std;



typedef long long int ll;

typedef long double ld;



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

#define pll pair<ll,ll>

#define mp make_pair

#define ff first

#define ss second

#define pb push_back

#define mod 1000000007

#define lp(start,end) for(ll i=start;i<=end;i++) 

#define deb1(a) cout<<#a<<" = "<<(a)<<endl;

#define deb2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;

#define deb3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;





ll modu(ll a, ll b)

{

	ll ans =1;

	while(b>0)

	{

		if(b&1)

		ans = (ans*a)%mod;

		b/=2;

		a = (a*a)%mod;

	}

	return ans;

}



ll n,w;

ll we[107],v[107];

ll dp[107][100007];



ll fun(ll x, ll curr)

{

	if(dp[x][curr]!=-1)

		return dp[x][curr];

	if(x==n)

	{

		if(curr-we[x] >=0)

			dp[x][curr] = v[x];

		else

			dp[x][curr] = 0; 

	}else {

	if(curr-we[x]>=0)

		dp[x][curr] = max(fun(x+1,curr),fun(x+1,curr-we[x]) + v[x]);

	else

		dp[x][curr] = fun(x+1,curr);

}

//	deb3(x,curr,dp[x][curr]);

	return dp[x][curr];

}



int main()

{

	fastio

	cin >> n >> w;

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

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

	}

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

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

			dp[i][j]=-1;



	cout << fun(1,w) << endl;;

	return 0;	

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



ll n, a[maxn], w[maxn], s;

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

		for (int j = s - w; j >= 0; j--) {

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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

}

#ifdef _MSC_VER

#include <intrin.h>

#define __builtin_popcount __popcnt

#ifdef _WIN64

#define __builtin_popcountll __popcnt64

#else

inline int __builtin_popcountll(__int64 a) {

	return __builtin_popcount((unsigned int)a) + __builtin_popcount(a >> 32);

}

#endif

#endif

using ll = long long;

using 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 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//be careful from the multiplication while using this define 

#define TC int t;cin>>t;while(t--)

//</DEFINE>

//<FUNCTIONS>

//</FUNCTIONS>	

int main() {

	Fast();

	int n, cpcty;

	cin >> n >> cpcty;

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

	vector<pair<ll, ll>>v(n);

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

	for (int i = v[n - 1].first; i <= cpcty; i++)dp[n - 1][i] = v[n - 1].second;

	for (int i = n - 2; i >= 0; i--) {

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

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

			else dp[i][j] = dp[i + 1][j];

		}

	}

	cout << dp[0][cpcty] << endl;

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

using namespace std;

const int maxn = 1e5 + 5;

typedef long long ll;

int main(){

	ll dp[maxn];

	ll n,W;

	ll w[105],v[105];

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

	scanf("%lld%lld",&n,&W);

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

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

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

		for(ll j = W;j >= 1;j--){

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

		}

	}

	printf("%lld\n",dp[W]);

	return 0;

}

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

}

#ifdef _MSC_VER

#include <intrin.h>

#define __builtin_popcount __popcnt

#ifdef _WIN64

#define __builtin_popcountll __popcnt64

#else

inline int __builtin_popcountll(__int64 a) {

	return __builtin_popcount((unsigned int)a) + __builtin_popcount(a >> 32);

}

#endif

#endif

using ll = long long;

using 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 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//be careful from the multiplication while using this define 

#define TC int t;cin>>t;while(t--)

//</DEFINE>

//<FUNCTIONS>

//</FUNCTIONS>	

int main() {

	Fast();

	int n, cpcty;

	cin >> n >> cpcty;

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

	vector<pair<ll, ll>>v(n);

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

	for (int i = v[n - 1].first; i <= cpcty; i++)dp[n - 1][i] = v[n - 1].second;

	for (int i = n - 2; i >= 0; i--) {

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

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

			else dp[i][j] = dp[i + 1][j];

		}

	}

	cout << dp[0][cpcty] << endl;

}