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.6169219703998823x):
/*

     _              ,_,                 

    / \   _ __, ___,| |__   __ _,_ __  

   / ^ \ | '_ \/ _ \| '_ \ / _` | /_/  

  /-/-\-\|-| |--| |-|-|_)-|-(_|-|-|    

 /_/   \_\_| |__| |_|_.__/ \__,_|_|    

 

*/

#include <bits/stdc++.h>

using namespace std;

 

#define int long long int

#define ld long double

#define ll long long

#define pb push_back

#define F first

#define S second

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

#define rep(i,a,n)   for(int i=a ; i<n ; i++)

 

typedef vector<ll> vi;

typedef pair<ll,ll> pii;

typedef vector<pii> vpii;

typedef vector<vi> vvi;

typedef map<ll,ll> mii;

typedef map<char,ll> mci;

 

ll gcd(ll a, ll b){

	if(b==0)return a;

	else return gcd(b, a%b);

}



signed main(){

    ll test=1;

    // cin>>test;

    while(test--){

        ll n, w; cin>>n>>w;

        vi wt(n), val(n);

        rep(i, 0, n)cin>>wt[i]>>val[i];

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

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

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

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

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

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

        	}

        }

        cout<<dp[n][w]<<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.799805283667561x):
/*

     _              ,_,                 

    / \   _ __, ___,| |__   __ _,_ __  

   / ^ \ | '_ \/ _ \| '_ \ / _` | /_/  

  /-/-\-\|-| |--| |-|-|_)-|-(_|-|-|    

 /_/   \_\_| |__| |_|_.__/ \__,_|_|    

 

*/

#include <bits/stdc++.h>

using namespace std;

 

#define int long long int

#define ld long double

#define ll long long

#define pb push_back

#define F first

#define S second

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

#define rep(i,a,n)   for(int i=a ; i<n ; i++)

 

typedef vector<ll> vi;

typedef pair<ll,ll> pii;

typedef vector<pii> vpii;

typedef vector<vi> vvi;

typedef map<ll,ll> mii;

typedef map<char,ll> mci;

 

ll gcd(ll a, ll b){

	if(b==0)return a;

	else return gcd(b, a%b);

}



signed main(){

    ll test=1;

    // cin>>test;

    while(test--){

        ll n, w; cin>>n>>w;

        vi wt(n), val(n);

        rep(i, 0, n)cin>>wt[i]>>val[i];

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

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

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

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

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

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

        	}

        }

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

 

    }    

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



#define SORT(v) sort(v.begin(),v.end())

#define si(n) scanf("%d",&n)

#define sii(n,m) scanf("%d %d",&n,&m)

#define sl(n) scanf("%lld",&n)

#define sll(n,m) scanf("%lld %lld",&n,&m)

#define ss(cad) scanf("%s",cad)

#define fst first

#define scn second

#define DBG(x) cerr << #x << " = " << (x) << endl; 

#define M 1000000007

#define N_MAX 100010



using namespace std;



typedef long long ll;

typedef vector<int> vi;

typedef vector<bool> vb;

typedef vector<ll> vl;

typedef pair<int,int> pi;

typedef pair<ll, ll> pll;

typedef vector<pi> vp;



ll dp[110][100100];

ll pesos[110];

ll costo[110];



int main(){

	int n, w;

	sii(n, w);



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

		sl(pesos[i]);

		sl(costo[i]);

	}



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

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

			ll ans = 0;

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

			if(j-pesos[i] >= 0)

				ans = max(ans, costo[i] + dp[i-1][j-pesos[i]]);

			dp[i][j] = ans;

		}

	}

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

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.387129925323414x):
/*

     _              ,_,                 

    / \   _ __, ___,| |__   __ _,_ __  

   / ^ \ | '_ \/ _ \| '_ \ / _` | /_/  

  /-/-\-\|-| |--| |-|-|_)-|-(_|-|-|    

 /_/   \_\_| |__| |_|_.__/ \__,_|_|    

 

*/

#include <bits/stdc++.h>

using namespace std;

 

#define int long long int

#define ld long double

#define ll long long

#define pb push_back

#define F first

#define S second

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

#define rep(i,a,n)   for(int i=a ; i<n ; i++)

 

typedef vector<ll> vi;

typedef pair<ll,ll> pii;

typedef vector<pii> vpii;

typedef vector<vi> vvi;

typedef map<ll,ll> mii;

typedef map<char,ll> mci;

 

ll gcd(ll a, ll b){

	if(b==0)return a;

	else return gcd(b, a%b);

}



signed main(){

    ll test=1;

    // cin>>test;

    while(test--){

        ll n, w; cin>>n>>w;

        vi wt(n), val(n);

        rep(i, 0, n)cin>>wt[i]>>val[i];

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

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

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

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

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

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

        	}

        }

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

 

    }    

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

using namespace std;

#define int long long

int32_t main(){

    

	int n,w; 

	cin>>n>>w;

	int a[n+1],b[n+1]; 

	for(int i=0;i<n;i++)  cin>>a[i]>>b[i]; 

	

	int dp[100005];

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

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

		for(int j=w;j>=a[i-1];j--){

			dp[j] = max(dp[j], dp[j-a[i-1]]+b[i-1]);

		}

	} 

	cout<<dp[w]<<endl;

}


// Faster C++ solution for the same problem (measured speedup: 1.8012348395542441x):
/*

     _              ,_,                 

    / \   _ __, ___,| |__   __ _,_ __  

   / ^ \ | '_ \/ _ \| '_ \ / _` | /_/  

  /-/-\-\|-| |--| |-|-|_)-|-(_|-|-|    

 /_/   \_\_| |__| |_|_.__/ \__,_|_|    

 

*/

#include <bits/stdc++.h>

using namespace std;

 

#define int long long int

#define ld long double

#define ll long long

#define pb push_back

#define F first

#define S second

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

#define rep(i,a,n)   for(int i=a ; i<n ; i++)

 

typedef vector<ll> vi;

typedef pair<ll,ll> pii;

typedef vector<pii> vpii;

typedef vector<vi> vvi;

typedef map<ll,ll> mii;

typedef map<char,ll> mci;

 

ll gcd(ll a, ll b){

	if(b==0)return a;

	else return gcd(b, a%b);

}



signed main(){

    ll test=1;

    // cin>>test;

    while(test--){

        ll n, w; cin>>n>>w;

        vi wt(n), val(n);

        rep(i, 0, n)cin>>wt[i]>>val[i];

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

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

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

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

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

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

        	}

        }

        cout<<dp[n][w]<<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.6000306454044084x):
#include <bits/stdc++.h>

using namespace std;

int  main(){

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

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

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

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

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

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

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

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

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

        	}

        }

        cout<<dp[n][w]<<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.788188163891401x):
#include <bits/stdc++.h>

using namespace std;

int  main(){

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

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

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

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

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

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

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

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

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

        	}

        }

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

 

     

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



#define SORT(v) sort(v.begin(),v.end())

#define si(n) scanf("%d",&n)

#define sii(n,m) scanf("%d %d",&n,&m)

#define sl(n) scanf("%lld",&n)

#define sll(n,m) scanf("%lld %lld",&n,&m)

#define ss(cad) scanf("%s",cad)

#define fst first

#define scn second

#define DBG(x) cerr << #x << " = " << (x) << endl; 

#define M 1000000007

#define N_MAX 100010



using namespace std;



typedef long long ll;

typedef vector<int> vi;

typedef vector<bool> vb;

typedef vector<ll> vl;

typedef pair<int,int> pi;

typedef pair<ll, ll> pll;

typedef vector<pi> vp;



ll dp[110][100100];

ll pesos[110];

ll costo[110];



int main(){

	int n, w;

	sii(n, w);



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

		sl(pesos[i]);

		sl(costo[i]);

	}



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

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

			ll ans = 0;

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

			if(j-pesos[i] >= 0)

				ans = max(ans, costo[i] + dp[i-1][j-pesos[i]]);

			dp[i][j] = ans;

		}

	}

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

    return 0;

}

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

using namespace std;

int  main(){

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

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

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

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

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

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

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

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

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

        	}

        }

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

 

     

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

using namespace std;

#define int long long

int32_t main(){

    

	int n,w; 

	cin>>n>>w;

	int a[n+1],b[n+1]; 

	for(int i=0;i<n;i++)  cin>>a[i]>>b[i]; 

	

	int dp[100005];

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

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

		for(int j=w;j>=a[i-1];j--){

			dp[j] = max(dp[j], dp[j-a[i-1]]+b[i-1]);

		}

	} 

	cout<<dp[w]<<endl;

}


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

using namespace std;

int  main(){

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

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

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

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

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

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

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

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

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

        	}

        }

        cout<<dp[n][w]<<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.6131142309258206x):
#include<bits/stdc++.h>

#define ll long long

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

#define PI acos(-1)

#define endl "\n"

#define fx(x) fixed<<setprecision(x)

#define sz(s) s.size()

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

#define allr(v) (v).rbegin(),(v).rend()

const double eps=1e-9;

const int mod=1e9+7;

int dx[]={-1,-1,-1,0,0,1,1,1};

int dy[]={-1,0,1,-1,1,-1,0,1};

ll gcd(ll x,ll y) {return(!y)?x:gcd(y,x%y);}

ll lcm(ll x,ll y) {return((x/gcd(x,y))*y);}

using namespace std;

void fast(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

}

int n,w;

vector<pair<ll,ll> >v;

ll dp[101][100001];

ll solve(int idx,int we){

    if(idx==n)return 0;

    ll &ret=dp[idx][we];

    if(ret){return ret;}

    ret=solve(idx+1,we);

    if(v[idx].second+we<=w)ret=max(ret,v[idx].first+solve(idx+1,v[idx].second+we));

    return ret;

}

int main()

{

    cin>>n>>w;

    v.resize(n);

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

        cin>>v[i].second>>v[i].first;

    }

    cout<<solve(0,0);

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

#define ll long long

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

#define PI acos(-1)

#define endl "\n"

#define fx(x) fixed<<setprecision(x)

#define sz(s) s.size()

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

#define allr(v) (v).rbegin(),(v).rend()

const double eps=1e-9;

const int mod=1e9+7;

int dx[]={-1,-1,-1,0,0,1,1,1};

int dy[]={-1,0,1,-1,1,-1,0,1};

ll gcd(ll x,ll y) {return(!y)?x:gcd(y,x%y);}

ll lcm(ll x,ll y) {return((x/gcd(x,y))*y);}

using namespace std;

void fast(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

}

int n,w;

vector<pair<ll,ll> >v;

ll dp[101][100001];

ll solve(int idx,int we){

    if(idx==n)return 0;

    ll &ret=dp[idx][we];

    if(ret){return ret;}

    ret=solve(idx+1,we);

    if(v[idx].second+we<=w)ret=max(ret,v[idx].first+solve(idx+1,v[idx].second+we));

    return ret;

}

int main()

{

    cin>>n>>w;

    v.resize(n);

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

        cin>>v[i].second>>v[i].first;

    }

    cout<<solve(0,0);

    return 0;

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



#define SORT(v) sort(v.begin(),v.end())

#define si(n) scanf("%d",&n)

#define sii(n,m) scanf("%d %d",&n,&m)

#define sl(n) scanf("%lld",&n)

#define sll(n,m) scanf("%lld %lld",&n,&m)

#define ss(cad) scanf("%s",cad)

#define fst first

#define scn second

#define DBG(x) cerr << #x << " = " << (x) << endl; 

#define M 1000000007

#define N_MAX 100010



using namespace std;



typedef long long ll;

typedef vector<int> vi;

typedef vector<bool> vb;

typedef vector<ll> vl;

typedef pair<int,int> pi;

typedef pair<ll, ll> pll;

typedef vector<pi> vp;



ll dp[110][100100];

ll pesos[110];

ll costo[110];



int main(){

	int n, w;

	sii(n, w);



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

		sl(pesos[i]);

		sl(costo[i]);

	}



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

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

			ll ans = 0;

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

			if(j-pesos[i] >= 0)

				ans = max(ans, costo[i] + dp[i-1][j-pesos[i]]);

			dp[i][j] = ans;

		}

	}

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

    return 0;

}

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

#define ll long long

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

#define PI acos(-1)

#define endl "\n"

#define fx(x) fixed<<setprecision(x)

#define sz(s) s.size()

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

#define allr(v) (v).rbegin(),(v).rend()

const double eps=1e-9;

const int mod=1e9+7;

int dx[]={-1,-1,-1,0,0,1,1,1};

int dy[]={-1,0,1,-1,1,-1,0,1};

ll gcd(ll x,ll y) {return(!y)?x:gcd(y,x%y);}

ll lcm(ll x,ll y) {return((x/gcd(x,y))*y);}

using namespace std;

void fast(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

}

int n,w;

vector<pair<ll,ll> >v;

ll dp[101][100001];

ll solve(int idx,int we){

    if(idx==n)return 0;

    ll &ret=dp[idx][we];

    if(ret){return ret;}

    ret=solve(idx+1,we);

    if(v[idx].second+we<=w)ret=max(ret,v[idx].first+solve(idx+1,v[idx].second+we));

    return ret;

}

int main()

{

    cin>>n>>w;

    v.resize(n);

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

        cin>>v[i].second>>v[i].first;

    }

    cout<<solve(0,0);

    return 0;

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

using namespace std;

#define int long long

int32_t main(){

    

	int n,w; 

	cin>>n>>w;

	int a[n+1],b[n+1]; 

	for(int i=0;i<n;i++)  cin>>a[i]>>b[i]; 

	

	int dp[100005];

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

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

		for(int j=w;j>=a[i-1];j--){

			dp[j] = max(dp[j], dp[j-a[i-1]]+b[i-1]);

		}

	} 

	cout<<dp[w]<<endl;

}


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

#define ll long long

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

#define PI acos(-1)

#define endl "\n"

#define fx(x) fixed<<setprecision(x)

#define sz(s) s.size()

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

#define allr(v) (v).rbegin(),(v).rend()

const double eps=1e-9;

const int mod=1e9+7;

int dx[]={-1,-1,-1,0,0,1,1,1};

int dy[]={-1,0,1,-1,1,-1,0,1};

ll gcd(ll x,ll y) {return(!y)?x:gcd(y,x%y);}

ll lcm(ll x,ll y) {return((x/gcd(x,y))*y);}

using namespace std;

void fast(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

}

int n,w;

vector<pair<ll,ll> >v;

ll dp[101][100001];

ll solve(int idx,int we){

    if(idx==n)return 0;

    ll &ret=dp[idx][we];

    if(ret){return ret;}

    ret=solve(idx+1,we);

    if(v[idx].second+we<=w)ret=max(ret,v[idx].first+solve(idx+1,v[idx].second+we));

    return ret;

}

int main()

{

    cin>>n>>w;

    v.resize(n);

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

        cin>>v[i].second>>v[i].first;

    }

    cout<<solve(0,0);

    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.6225675724774384x):
//In The Name of ALLAH//



/*      ______     _    _______

       |  ___ \   | |  |  ____/   /\

       | |   \ \  | |  | |       /  \

       | |___/ /  | |  | |___   / /\ \

       |     _/   | |  |  __/  / /__\ \

       | |\ \     | |  | |    / ______ \

       | | \ \    | |  | |   / /      \ \

       |_|  \_\   |_|  |_|  /_/        \_\

*/



#include<bits/stdc++.h>



//#define FILEIO

#define ll long long



using namespace std;



const int SZ = 100005;

const int LIM = 1000000000;

const double EPS = 1e-9;

const int MOD = 100000008;

const int INF = ( 1 << 30 ) - 1;

const double PI = 2 * acos( 0.0 );



template <class T> T MIN(T a, T b) { return (a < b) ? a : b; }

template <class T> T MAX(T a, T b) { return (a > b) ? a : b; }

template <class T> void SWAP(T &a, T &b) { T c; c = a; a = b; b = c; }

template <class T> T GCD(T a, T b) { T c; while(b > 0) { c = a % b; a = b; b = c; } return a; }



bool CMP(int a, int b)

{

    return (a > b);

}



void solve()

{

    ll n, nw, wt[110], v[110];

    cin >> n >> nw;

    ll kp[n + 5][nw + 5];

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

    {

        for(int j = 0; j <= nw; j++)

        {

            kp[i][j] = 0;

        }

    }

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

    {

        cin >> wt[i] >> v[i];

    }

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

    {

        for(int j = 1; j <= nw; j++)

        {

            if(wt[i] > j)

            {

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

            }

            else

            {

                kp[i][j] = max(kp[i - 1][j], kp[i - 1][j - wt[i]] + v[i]);

            }

        }

    }



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

    {

        for(int j = 0; j <= nw; j++)

        {

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

        }

        cout << endl;

    }*/



    cout << kp[n][nw] << endl;

}



int main()

{

    #ifdef FILEIO

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

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

    #endif



    //int tc;



    //cin >> tc;

    //while(tc--)

    {

        solve();

    }



    return 0;

}