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

#define INF 0x3f3f3f3f

#define LL long long

using namespace std;

const int maxn = 1e5+10;

int a[maxn];

LL b[maxn];

LL dp[maxn];

int main()

{

    int n,w;

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

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

    {

        scanf("%d%lld",a+i,b+i);

    }

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

    {

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

        {

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

            {

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

            }

        }

    }

    printf("%lld\n",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.626089811097078x):
#include<iostream>

#include<cmath>

#include<cstring>

#include<cstdio>

using namespace std;

typedef long long ll;

ll a[110],b[110];

ll dp[100005];

int main()

{

	ll n,w;

	cin>>n>>w;

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

		cin>>a[i]>>b[i];

	}



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

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

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

		}

	}

	

	cout<<dp[w];



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

#include<cmath>

#include<cstring>

#include<cstdio>

using namespace std;

typedef long long ll;

ll a[110],b[110];

ll dp[100005];

int main()

{

	ll n,w;

	cin>>n>>w;

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

		cin>>a[i]>>b[i];

	}



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

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

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

		}

	}

	

	cout<<dp[w];



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

#include<cmath>

#include<cstring>

#include<cstdio>

using namespace std;

typedef long long ll;

ll a[110],b[110];

ll dp[100005];

int main()

{

	ll n,w;

	cin>>n>>w;

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

		cin>>a[i]>>b[i];

	}



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

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

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

		}

	}

	

	cout<<dp[w];



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

using namespace std;



#define ll long long int 

#define oo (1L<<60)



int N; int CAP;

ll memo [100005][100];

int pesos [100005];

int valores [100005];



ll mochila(int cap, int it){

	if(cap < 0) return -oo;

	if(!cap || it == -1) return 0;

	if(memo[cap][it]) return memo[cap][it];

	return memo[cap][it] =max(mochila(cap, it-1), 

							  valores[it]+mochila(cap-pesos[it], it-1));

}



int main() {

	cin>>N>>CAP;

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

		cin>>pesos[i]>>valores[i];

	cout<<mochila(CAP, N-1)<<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.8019460729661487x):
#include <bits/stdc++.h>

using namespace std;



#define ll long long int 

#define oo (1L<<60)



int N; int CAP;

ll memo [100005][100];

int pesos [100005];

int valores [100005];



ll mochila(int cap, int it){

	if(cap < 0) return -oo;

	if(!cap || it == -1) return 0;

	if(memo[cap][it]) return memo[cap][it];

	return memo[cap][it] =max(mochila(cap, it-1), 

							  valores[it]+mochila(cap-pesos[it], it-1));

}



int main() {

	cin>>N>>CAP;

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

		cin>>pesos[i]>>valores[i];

	cout<<mochila(CAP, N-1)<<endl;

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

using namespace std;



#define ll long long int 

#define oo (1L<<60)



int N; int CAP;

ll memo [100005][100];

int pesos [100005];

int valores [100005];



ll mochila(int cap, int it){

	if(cap < 0) return -oo;

	if(!cap || it == -1) return 0;

	if(memo[cap][it]) return memo[cap][it];

	return memo[cap][it] =max(mochila(cap, it-1), 

							  valores[it]+mochila(cap-pesos[it], it-1));

}



int main() {

	cin>>N>>CAP;

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

		cin>>pesos[i]>>valores[i];

	cout<<mochila(CAP, N-1)<<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.558230890844121x):
#include <bits/stdc++.h>

using namespace std;

     

int main(){

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n,w;

  cin >> n >> w;

  vector<int> vi(n);

  vector<long long> wi(n);

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

    cin >> wi[i] >> vi[i];

  }

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

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

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

      if(i==0 || j==0){

	dp[i][j] = 0;

      }else{

	if(j>=wi[i-1]){

	  dp[i][j] = max(dp[i-1][j],dp[i-1][j-wi[i-1]]+vi[i-1]);

	}else{

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

	}

      }

    }

  }

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

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

using namespace std;

     

int main(){

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n,w;

  cin >> n >> w;

  vector<int> vi(n);

  vector<long long> wi(n);

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

    cin >> wi[i] >> vi[i];

  }

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

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

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

      if(i==0 || j==0){

	dp[i][j] = 0;

      }else{

	if(j>=wi[i-1]){

	  dp[i][j] = max(dp[i-1][j],dp[i-1][j-wi[i-1]]+vi[i-1]);

	}else{

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

	}

      }

    }

  }

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

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

using namespace std;

     

int main(){

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n,w;

  cin >> n >> w;

  vector<int> vi(n);

  vector<long long> wi(n);

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

    cin >> wi[i] >> vi[i];

  }

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

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

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

      if(i==0 || j==0){

	dp[i][j] = 0;

      }else{

	if(j>=wi[i-1]){

	  dp[i][j] = max(dp[i-1][j],dp[i-1][j-wi[i-1]]+vi[i-1]);

	}else{

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

	}

      }

    }

  }

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

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

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

typedef long long ll;

ll c[100005];

ll ans,n,w;

ll a[100005],b[1000005];

int main()

{

	ll i,j,k,x,y,t;

	cin>>n>>w;

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

	cin>>a[i]>>b[i];

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

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

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

	

	cout<<c[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.806109009983729x):
//#include <bits/stdc++.h>

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

typedef long long ll;

ll c[100005];

ll ans,n,w;

ll a[100005],b[1000005];

int main()

{

	ll i,j,k,x,y,t;

	cin>>n>>w;

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

	cin>>a[i]>>b[i];

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

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

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

	

	cout<<c[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.398993175331788x):
//#include <bits/stdc++.h>

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

typedef long long ll;

ll c[100005];

ll ans,n,w;

ll a[100005],b[1000005];

int main()

{

	ll i,j,k,x,y,t;

	cin>>n>>w;

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

	cin>>a[i]>>b[i];

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

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

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

	

	cout<<c[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.5620726101046474x):
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define ld long double

#define uu unsigned

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

#define MOD 1000000007

#define pi pair<int,int>

#define pl pair<ll,ll>

#define mkp make_pair

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

#define ss second

#define ff first

#define mit map<ll,ll>::iterator

#define sit unordered_set<ll>::iterator

#define lit list<ll>::iterator

#define vi vector<int>

#define vl vector<ll>

#define pb push_back

#define pf push_front

#define printf __mingw_printf

#define printcas cout<<"Case "<<cas<<": "

#define _ continue;

#define endl '\n'

#define __ cout<<endl;continue;

#define vec4d(nam,type,a,b,c,d,fix) vector<vector<vector<vector<type>>>> nam(a,vector<vector<vector<type>>>(b,vector<vector<type>>(c,vector<type>(d,fix))))

int main()

{

     io;

    //string hudai(1000000,'a');

    int T=1;

   // cin>>T;

     for(int cas=1;cas<=T;cas++)

    {

        ll N,W;

        cin>>N>>W;

        vl w(N+1),v(N+1);

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

        {

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

        }

        vector<vl> dp(N+1,vl(W+1,0));

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

        {

            for(ll j=1;j<=W;j++)

            {

                if(w[i]<=j)

                {

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

                }

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

            }

        }

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

using namespace std;

#define ll long long

#define ld long double

#define uu unsigned

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

#define MOD 1000000007

#define pi pair<int,int>

#define pl pair<ll,ll>

#define mkp make_pair

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

#define ss second

#define ff first

#define mit map<ll,ll>::iterator

#define sit unordered_set<ll>::iterator

#define lit list<ll>::iterator

#define vi vector<int>

#define vl vector<ll>

#define pb push_back

#define pf push_front

#define printf __mingw_printf

#define printcas cout<<"Case "<<cas<<": "

#define _ continue;

#define endl '\n'

#define __ cout<<endl;continue;

#define vec4d(nam,type,a,b,c,d,fix) vector<vector<vector<vector<type>>>> nam(a,vector<vector<vector<type>>>(b,vector<vector<type>>(c,vector<type>(d,fix))))

int main()

{

     io;

    //string hudai(1000000,'a');

    int T=1;

   // cin>>T;

     for(int cas=1;cas<=T;cas++)

    {

        ll N,W;

        cin>>N>>W;

        vl w(N+1),v(N+1);

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

        {

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

        }

        vector<vl> dp(N+1,vl(W+1,0));

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

        {

            for(ll j=1;j<=W;j++)

            {

                if(w[i]<=j)

                {

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

                }

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

            }

        }

        cout<<dp[N][W];



    }

    return 0;

}