stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

long long dp[100005];

int main(){

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

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

            if(dp[j] == -1) continue;

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

    for(int i=0;i<=W;i++) ans = max(ans, dp[i]);

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

}

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

#define FIN         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define ii          pair<int,int>

#define F           first

#define S           second

#define pb          push_back

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

#define rall(x)     (x).rbegin(),(x).rend()

#define fore(i,a,b) for(int i = a;i < b; i+= 1)

#define forr(i,a)   for(int i = a; i >= 0; i--)

#define fori(i,m)   for(auto i = m.begin(); i != m.end(); i++) 

#define w(t)        while(t--)

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

#define cls(a,car)  memset(a,car,sizeof (a))

#define db(x)       cerr << #x << " is " << x << '\n'

#define FL          freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout);

#define EjecuteTime cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"

#define angle(x)    double(x * acos(-1) / 180.0)

using namespace std;

typedef long long   ll;

typedef vector<int> vi;

typedef vector<ii>  vii;

const int N = 1 * 1e5 + 5;

const ll mod = 1e9 + 7;

const double E = 1e-9;

//int dx[] = {1, 0}, dy[] = {0, 1};

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

//int dx[] = {2, 1, -1, -2, -2, -1, 1, 2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

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

// fflush(stdout)

// cout << flush

// a + b = a ^ b + 2 * (a & b)

int n, W;

int w[101], v[101];

ll dp[2][N];

ll f(int i, int cost){

    if(cost < 0)

        return -1e18;

    if(i == n)

        return 0;

    ll &ans = dp[i][cost];

    if(ans == -1){

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

    }return ans;

}

int main(){

    //FL;

    FIN;

    //optimizando memoria

    cin >> n >> W;

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

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

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

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

            ll &ans = dp[i & 1][cost];    

            if(i == n){

                ans = 0;

                continue;

            }

            ans = max(ans, dp[(i + 1) & 1][cost]);

            if(cost - w[i] >= 0)

                ans = max(ans, dp[(i + 1) & 1][cost - w[i]] + v[i]);

        }

    }

    cout << dp[0][W] << '\n';

    EjecuteTime;

    return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

#define endl '\n'

using namespace std;

int wi[100001], vi[100001];

long long dp[105][100005];



long long solve(int n, int w){

    if(n == 0 || w == 0) return 0;

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

    if(wi[n-1] > w){

        return dp[n-1][w] = solve(n-1, w);

    }

    return dp[n-1][w] = max(solve(n-1,w), solve(n-1,w-wi[n-1])+vi[n-1]);

}





int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(0);

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

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

    {

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



    };

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

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

            dp[i][j] = -1;

        }

    }

    cout << solve(n,w) << endl; 

    

    return 0;



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

using namespace std;

long long dp[100005];

int main(){

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

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

            if(dp[j] == -1) continue;

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

    for(int i=0;i<=W;i++) ans = max(ans, dp[i]);

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

}

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

#define endl '\n'

using namespace std;

int wi[100001], vi[100001];

long long dp[105][100005];



long long solve(int n, int w){

    if(n == 0 || w == 0) return 0;

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

    if(wi[n-1] > w){

        return dp[n-1][w] = solve(n-1, w);

    }

    return dp[n-1][w] = max(solve(n-1,w), solve(n-1,w-wi[n-1])+vi[n-1]);

}





int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(0);

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

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

    {

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



    };

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

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

            dp[i][j] = -1;

        }

    }

    cout << solve(n,w) << endl; 

    

    return 0;



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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.567436944225233x):
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#include<bits/stdc++.h>  

#define endl "\n"

using namespace std;

	typedef long long ll;

	const int maxn=105000;

	const int inf=0x3f3f3f3f;

	ll w[105];

	ll v[105];

	ll dp[maxn];

	ll n,m;

	int main(){

		IOS

		cin>>n>>m;

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

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

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

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

				if(j+w[i-1]<=m)

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

			

		ll ans=-1;

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

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

		cout<<ans<<endl;

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

using namespace std;

long long dp[100005];

int main(){

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

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

            if(dp[j] == -1) continue;

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

    for(int i=0;i<=W;i++) ans = max(ans, dp[i]);

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

}

// Faster C++ solution for the same problem (measured speedup: 1.7719022652023824x):
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#include<bits/stdc++.h>  

#define endl "\n"

using namespace std;

	typedef long long ll;

	const int maxn=105000;

	const int inf=0x3f3f3f3f;

	ll w[105];

	ll v[105];

	ll dp[maxn];

	ll n,m;

	int main(){

		IOS

		cin>>n>>m;

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

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

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

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

				if(j+w[i-1]<=m)

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

			

		ll ans=-1;

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

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

		cout<<ans<<endl;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

using namespace std;

const int maxn=100005;

const int inf=0x3f3f3f3f;

long long n,w,k,dp[maxn],a[maxn],v[maxn];

int main()

{

	cin>>n>>w;

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

	{

		cin>>a[i]>>v[i];

	}

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

	{

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

		{

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

		}

	}

	cout<<dp[w]<<endl;

	return 0;

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

using namespace std;

long long dp[100005];

int main(){

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

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

            if(dp[j] == -1) continue;

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

    for(int i=0;i<=W;i++) ans = max(ans, dp[i]);

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

}

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

using namespace std;

const int maxn=100005;

const int inf=0x3f3f3f3f;

long long n,w,k,dp[maxn],a[maxn],v[maxn];

int main()

{

	cin>>n>>w;

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

	{

		cin>>a[i]>>v[i];

	}

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

	{

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

		{

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

		}

	}

	cout<<dp[w]<<endl;

	return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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


#include<bits/stdc++.h>

#define ll long long int

using namespace std;

int main()

{

    ll item,weight;

    cin>>item>>weight;

    ll wt[item+5],value[item+5];

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

    {

        cin>>wt[i]>>value[i];

    }

    ll knapsack[item+5][weight+5];

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

    {

        for(int w=0; w<=weight; w++)

        {

            if(i==0 || w==0)

                knapsack[i][w]=0;

            else if(wt[i]<=w)

            {

                knapsack[i][w]=max(value[i]+knapsack[i-1][w-wt[i]],knapsack[i-1][w]);

            }

            else

                knapsack[i][w]=knapsack[i-1][w];

        }

    }

    cout<<knapsack[item][weight]<<endl;





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

using namespace std;

long long dp[100005];

int main(){

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

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

            if(dp[j] == -1) continue;

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

    for(int i=0;i<=W;i++) ans = max(ans, dp[i]);

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

}

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


#include<bits/stdc++.h>

#define ll long long int

using namespace std;

int main()

{

    ll item,weight;

    cin>>item>>weight;

    ll wt[item+5],value[item+5];

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

    {

        cin>>wt[i]>>value[i];

    }

    ll knapsack[item+5][weight+5];

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

    {

        for(int w=0; w<=weight; w++)

        {

            if(i==0 || w==0)

                knapsack[i][w]=0;

            else if(wt[i]<=w)

            {

                knapsack[i][w]=max(value[i]+knapsack[i-1][w-wt[i]],knapsack[i-1][w]);

            }

            else

                knapsack[i][w]=knapsack[i-1][w];

        }

    }

    cout<<knapsack[item][weight]<<endl;





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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

#include <cstring>



using namespace std;



int main(){

	//Number of items available and max capacity of Knapsack

	int items, capacity;

	cin >> items >> capacity;



	//Store the value sum for each combination of items with weight w

	long long dp[capacity+1];

	//set all dp values to zero in order to compare max value

	memset(dp,0,sizeof dp);



	//read every weight and value of item

	int weight, value;	

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

	{

		cin >> weight >> value;

		//cw is the current weight inside the knapsack

		for (int cw = capacity - weight;cw>=0;cw--){

			//Check max value between (don't put item, put item)

			//Then memoize current answer

			dp[cw + weight] = max(dp[cw + weight], dp[cw] + value);

		}

	}

	//Set answer to zero in order to compare max value

	long long answer = 0;

	//Loop through dp to get max possible value

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

	{

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

	}

	//Print max possible sum of values

	cout << answer << endl;



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

using namespace std;

long long dp[100005];

int main(){

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

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

            if(dp[j] == -1) continue;

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

    for(int i=0;i<=W;i++) ans = max(ans, dp[i]);

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

}

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

#include <cstring>



using namespace std;



int main(){

	//Number of items available and max capacity of Knapsack

	int items, capacity;

	cin >> items >> capacity;



	//Store the value sum for each combination of items with weight w

	long long dp[capacity+1];

	//set all dp values to zero in order to compare max value

	memset(dp,0,sizeof dp);



	//read every weight and value of item

	int weight, value;	

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

	{

		cin >> weight >> value;

		//cw is the current weight inside the knapsack

		for (int cw = capacity - weight;cw>=0;cw--){

			//Check max value between (don't put item, put item)

			//Then memoize current answer

			dp[cw + weight] = max(dp[cw + weight], dp[cw] + value);

		}

	}

	//Set answer to zero in order to compare max value

	long long answer = 0;

	//Loop through dp to get max possible value

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

	{

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

	}

	//Print max possible sum of values

	cout << answer << endl;



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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

using namespace std;



typedef long long ll;

ll solve(int n, int W, vector<int> &weight, vector<int> &value)

{

  vector<vector<pair<ll, ll>>> dp(W + 5, vector<pair<ll, ll>>(n + 5));

  ll ans = 0;

  for (int w = 1; w <= W; ++w)

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

    {

      if (w >= weight[i])

      {

        if (!i)

          dp[w][i].first = value[i];

        else

          dp[w][i].first = value[i] + max(dp[w - weight[i]][i - 1].first, dp[w - weight[i]][i - 1].second);

      }

      if (i)

        dp[w][i].second = max(dp[w][i - 1].first, dp[w][i - 1].second);

    }

  for (int w = 1; w <= W; ++w)

    ans = max(ans, max(dp[w][n - 1].first, dp[w][n - 1].second));

  return ans;

}



int main()

{

  ios_base::sync_with_stdio(false);

  cin.tie(0);

  cout.tie(0);



  vector<int> weight, value;

  int n, W, w, v;

  cin >> n >> W;

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

  {

    cin >> w >> v;

    weight.push_back(w), value.push_back(v);

  }

  cout << solve(n, W, weight, value);

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

using namespace std;

long long dp[100005];

int main(){

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

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

            if(dp[j] == -1) continue;

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

    for(int i=0;i<=W;i++) ans = max(ans, dp[i]);

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

}

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

using namespace std;



typedef long long ll;

ll solve(int n, int W, vector<int> &weight, vector<int> &value)

{

  vector<vector<pair<ll, ll>>> dp(W + 5, vector<pair<ll, ll>>(n + 5));

  ll ans = 0;

  for (int w = 1; w <= W; ++w)

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

    {

      if (w >= weight[i])

      {

        if (!i)

          dp[w][i].first = value[i];

        else

          dp[w][i].first = value[i] + max(dp[w - weight[i]][i - 1].first, dp[w - weight[i]][i - 1].second);

      }

      if (i)

        dp[w][i].second = max(dp[w][i - 1].first, dp[w][i - 1].second);

    }

  for (int w = 1; w <= W; ++w)

    ans = max(ans, max(dp[w][n - 1].first, dp[w][n - 1].second));

  return ans;

}



int main()

{

  ios_base::sync_with_stdio(false);

  cin.tie(0);

  cout.tie(0);



  vector<int> weight, value;

  int n, W, w, v;

  cin >> n >> W;

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

  {

    cin >> w >> v;

    weight.push_back(w), value.push_back(v);

  }

  cout << solve(n, W, weight, value);

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

using namespace std;

typedef long long int ll;



ll knapSack(ll n,ll v[],ll W,ll w[])

{

    ll K[n+5][W+5];

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

    {

        for (ll wt=0; wt<=W; wt++)

        {

            if (i==0 || wt==0)

                K[i][wt]=0;

            else if(w[i-1]<=wt)

                K[i][wt]=max(v[i-1]+K[i-1][wt-w[i-1]],K[i-1][wt]);

            else

                K[i][wt]=K[i-1][wt];

        }

    }

    return K[n][W];

}



int main(){

    ll n,W;

    cin>>n>>W;

    ll v[n+5],w[n+5];

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

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

    ll ans=knapSack(n,v,W,w);

    cout<<ans<<endl;

    return 0;

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

using namespace std;

long long dp[100005];

int main(){

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

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

            if(dp[j] == -1) continue;

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

    for(int i=0;i<=W;i++) ans = max(ans, dp[i]);

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

}

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

using namespace std;

typedef long long int ll;



ll knapSack(ll n,ll v[],ll W,ll w[])

{

    ll K[n+5][W+5];

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

    {

        for (ll wt=0; wt<=W; wt++)

        {

            if (i==0 || wt==0)

                K[i][wt]=0;

            else if(w[i-1]<=wt)

                K[i][wt]=max(v[i-1]+K[i-1][wt-w[i-1]],K[i-1][wt]);

            else

                K[i][wt]=K[i-1][wt];

        }

    }

    return K[n][W];

}



int main(){

    ll n,W;

    cin>>n>>W;

    ll v[n+5],w[n+5];

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

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

    ll ans=knapSack(n,v,W,w);

    cout<<ans<<endl;

    return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

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

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

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

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

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

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

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

using namespace std;

long long dp[100005];

int main(){

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

    int n, W;

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

    dp[0] = 0;

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

        int w, v;

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

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

            if(dp[j] == -1) continue;

            if(j+w <= W) dp[j+w] = max(dp[j+w], dp[j] + v);

        }

    }

    long long ans = 0;

    for(int i=0;i<=W;i++) ans = max(ans, dp[i]);

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

}

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

}