stablegradients/pie-gem5-pairs huggingface dataset:
// 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.394484566624557x):
#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const long long maxn=100000+50;

long long n,m,w[maxn],v[maxn],dp[maxn];

int main()

{

	cin>>n>>m;

	for(long long i=1;i<=n;i++)cin>>w[i]>>v[i];

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

	{

		for(long long j=m;j>=w[i];j--)

		{

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

		}

	}

	cout<<dp[m]<<endl;

	return 0;

}

//Phoenix-ZH
// 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.6193640216325096x):
#include<iostream>

using namespace std;



long long v[100000],w[100000],dp[100000];





main(){

	int k,m;

	cin>>k>>m;

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

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

	}	

	dp[0];

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

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

			if(j>=w[i])

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

		}

	}

	cout<<dp[m];

}
// 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.8014848204520675x):
#include<iostream>

using namespace std;



long long v[100000],w[100000],dp[100000];





main(){

	int k,m;

	cin>>k>>m;

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

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

	}	

	dp[0];

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

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

			if(j>=w[i])

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

		}

	}

	cout<<dp[m];

}
// 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.390290716857424x):
#include<iostream>

using namespace std;



long long v[100000],w[100000],dp[100000];





main(){

	int k,m;

	cin>>k>>m;

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

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

	}	

	dp[0];

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

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

			if(j>=w[i])

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

		}

	}

	cout<<dp[m];

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



using namespace std;



int main() {

    int N, W, w, v;

    cin >> N >> W;



    vector<long long> dp(W + 1);



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

        cin >> w >> v;

        for (int j = W; j >= w; j--) dp[j] = max(dp[j - w] + v, dp[j]);

    }



    cout << dp[W];



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



using namespace std;



int main() {

    int N, W, w, v;

    cin >> N >> W;



    vector<long long> dp(W + 1);



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

        cin >> w >> v;

        for (int j = W; j >= w; j--) dp[j] = max(dp[j - w] + v, dp[j]);

    }



    cout << dp[W];



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



using namespace std;



int main() {

    int N, W, w, v;

    cin >> N >> W;



    vector<long long> dp(W + 1);



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

        cin >> w >> v;

        for (int j = W; j >= w; j--) dp[j] = max(dp[j - w] + v, dp[j]);

    }



    cout << dp[W];



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

using namespace std;

#define ll long long int

ll w[100+5];

ll v[100+5];

ll dp[100+5][100000+5];



ll ans(int n, int wt){

    if(n<0) return 0;

if(dp[n][wt]!=-1) return dp[n][wt];

if(w[n]>wt) return dp[n][wt] = ans(n-1,wt);

else{

    return dp[n][wt] = max(ans(n-1,wt-w[n])+v[n], ans(n-1,wt));

}

}

int main(){

    int n, W;

    cin >> n >> W;

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

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

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

            dp[i][j] = -1;

        }

    }

    cout << ans(n-1,W);

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

using namespace std;

#define ll long long int

ll w[100+5];

ll v[100+5];

ll dp[100+5][100000+5];



ll ans(int n, int wt){

    if(n<0) return 0;

if(dp[n][wt]!=-1) return dp[n][wt];

if(w[n]>wt) return dp[n][wt] = ans(n-1,wt);

else{

    return dp[n][wt] = max(ans(n-1,wt-w[n])+v[n], ans(n-1,wt));

}

}

int main(){

    int n, W;

    cin >> n >> W;

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

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

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

            dp[i][j] = -1;

        }

    }

    cout << ans(n-1,W);

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

using namespace std;

#define ll long long int

ll w[100+5];

ll v[100+5];

ll dp[100+5][100000+5];



ll ans(int n, int wt){

    if(n<0) return 0;

if(dp[n][wt]!=-1) return dp[n][wt];

if(w[n]>wt) return dp[n][wt] = ans(n-1,wt);

else{

    return dp[n][wt] = max(ans(n-1,wt-w[n])+v[n], ans(n-1,wt));

}

}

int main(){

    int n, W;

    cin >> n >> W;

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

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

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

            dp[i][j] = -1;

        }

    }

    cout << ans(n-1,W);

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

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

}
// 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.5904305406444736x):
#include<iostream>

#include<vector>

#define lli long long int

#include<climits>

#include<unordered_map>

#include<algorithm>

#include<bitset>

#include<map>

#define pb push_back

using namespace std;



int main()

{

    lli n,w;

    cin>>n>>w;

    vector<lli>val(n);

    vector<lli>wt(n);

    

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

        cin>>wt[i];

        cin>>val[i];

    }

    

    vector<vector<lli>>dp(n,vector<lli>(w+1,0));

    

    lli i,j;

    for(i=n-1,j=0;j<=w;j++) if(j+wt[i]<=w) dp[i][j]=val[i];

    

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

    {

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

        {

            if(j+wt[i]<=w)

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

            else

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

        }

    }

    

    

    cout<<dp[0][0]<<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.7815856287504497x):
#include<iostream>

#include<vector>

#define lli long long int

#include<climits>

#include<unordered_map>

#include<algorithm>

#include<bitset>

#include<map>

#define pb push_back

using namespace std;



int main()

{

    lli n,w;

    cin>>n>>w;

    vector<lli>val(n);

    vector<lli>wt(n);

    

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

        cin>>wt[i];

        cin>>val[i];

    }

    

    vector<vector<lli>>dp(n,vector<lli>(w+1,0));

    

    lli i,j;

    for(i=n-1,j=0;j<=w;j++) if(j+wt[i]<=w) dp[i][j]=val[i];

    

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

    {

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

        {

            if(j+wt[i]<=w)

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

            else

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

        }

    }

    

    

    cout<<dp[0][0]<<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.352841583712893x):
#include<iostream>

#include<vector>

#define lli long long int

#include<climits>

#include<unordered_map>

#include<algorithm>

#include<bitset>

#include<map>

#define pb push_back

using namespace std;



int main()

{

    lli n,w;

    cin>>n>>w;

    vector<lli>val(n);

    vector<lli>wt(n);

    

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

        cin>>wt[i];

        cin>>val[i];

    }

    

    vector<vector<lli>>dp(n,vector<lli>(w+1,0));

    

    lli i,j;

    for(i=n-1,j=0;j<=w;j++) if(j+wt[i]<=w) dp[i][j]=val[i];

    

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

    {

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

        {

            if(j+wt[i]<=w)

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

            else

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

        }

    }

    

    

    cout<<dp[0][0]<<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.7830007130633594x):
#include<iostream>

#include<vector>

#define lli long long int

#include<climits>

#include<unordered_map>

#include<algorithm>

#include<bitset>

#include<map>

#define pb push_back

using namespace std;



int main()

{

    lli n,w;

    cin>>n>>w;

    vector<lli>val(n);

    vector<lli>wt(n);

    

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

        cin>>wt[i];

        cin>>val[i];

    }

    

    vector<vector<lli>>dp(n,vector<lli>(w+1,0));

    

    lli i,j;

    for(i=n-1,j=0;j<=w;j++) if(j+wt[i]<=w) dp[i][j]=val[i];

    

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

    {

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

        {

            if(j+wt[i]<=w)

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

            else

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

        }

    }

    

    

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

    

}