stablegradients/pie-gem5-pairs huggingface dataset:
// 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.8036880835995428x):
//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;

}
// 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.394437131254524x):
//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;

}
// 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.8051207235306777x):
//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;

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

using namespace std;

long long ar [110000];

 

int main ()

{

int n,w;

int wi,vi;

cin >>n>>w;

int i,j;

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

{

cin >>wi>>vi;

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

{

ar [j + wi] = max (ar[j + wi] , ar [j] + vi);

}

}

long long t ;

t = 0;

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

{

t = max (t , ar [i]);

}

cout <<t<<'\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.8043825016433053x):
#include <bits/stdc++.h>

using namespace std;

long long ar [110000];

 

int main ()

{

int n,w;

int wi,vi;

cin >>n>>w;

int i,j;

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

{

cin >>wi>>vi;

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

{

ar [j + wi] = max (ar[j + wi] , ar [j] + vi);

}

}

long long t ;

t = 0;

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

{

t = max (t , ar [i]);

}

cout <<t<<'\n';

 

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

using namespace std;

long long ar [110000];

 

int main ()

{

int n,w;

int wi,vi;

cin >>n>>w;

int i,j;

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

{

cin >>wi>>vi;

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

{

ar [j + wi] = max (ar[j + wi] , ar [j] + vi);

}

}

long long t ;

t = 0;

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

{

t = max (t , ar [i]);

}

cout <<t<<'\n';

 

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

using namespace std;

long long ar [110000];

 

int main ()

{

int n,w;

int wi,vi;

cin >>n>>w;

int i,j;

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

{

cin >>wi>>vi;

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

{

ar [j + wi] = max (ar[j + wi] , ar [j] + vi);

}

}

long long t ;

t = 0;

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

{

t = max (t , ar [i]);

}

cout <<t<<'\n';

 

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

#include <cstdio>

#include <cstring>

using namespace std;



typedef long long llt;



const int MaxN = 100 + 5, MaxW = 100000 + 5;



int N, W;

int w[MaxN]; llt v[MaxN];

llt dp[MaxW];



void init() {

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

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

    scanf("%d %lld", &w[i], &v[i]);

}



void solve() {

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

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

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

  llt ans = 0;

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

  cout << ans << endl;

}



int main() {

  init();

  solve();

  return 0;

}

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



const int MaxN = 100 + 5, MaxM = 100000 + 5;



int N, M;

int W[MaxN], V[MaxN];

long long Dp[MaxM];



template <typename T>

inline T max(T x, T y) { return x > y ? x : y; }



void init() {

  scanf("%d %d", &N, &M);

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

    scanf("%d %d", &W[i], &V[i]);

}



void solve() {

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

    for (int j = M; j >= W[i]; --j)

      Dp[j] = max(Dp[j], Dp[j - W[i]] + V[i]);

  long long ans = 0;

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

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

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

}



int main() {

  init();

  solve();

  return 0;

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

using namespace std;

typedef long long ll;

#define pb push_back

#define mod 1000000007

#define null NULL

#define test cout<<"#"

#define maX 1000000000

 

ll ans[100001];



void solve(vector<ll> &w, vector<ll> &v, ll n, ll wt)

{	

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

	{

		for(ll y = wt; y>=0; y--)

		{

			if(w[x]<=y)

				ans[y] = max(ans[y], ans[y - w[x]]+v[x]);

		}

	}

}



int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(0);

	memset(ans, 0, sizeof(ans));

    ll n, w;

	cin>>n>>w;

    vector<ll> a(n);

	vector<ll> b(n);

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

	{

		cin>>a[x];

		cin>>b[x];

	}

	solve(a, b, n, w);

	cout<<ans[w];

}

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

using namespace std;

typedef long long ll;

#define mod 1000000007

#define pb push_back

#define test cout<<"#"



int main()

{

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	ll n, wt;

	cin>>n>>wt;

	vector<ll> w(n);

	vector<ll> val(n);

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

		cin>>w[x]>>val[x];

	ll ans[wt+1] ={0};

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

	{

		for(ll y = wt; y>=0; y--)

		{

			if(w[x]<=y)

				ans[y] = max(ans[y], ans[y-w[x]]+val[x]);

		}

	}

	cout<<ans[wt];

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

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <queue>

#include <chrono>

#include <stack>

#include <string>

#include <bitset>

#include <unordered_map>

#include <cstdio>

#include <limits>

#include <vector>

#include <climits>

#include <cstring>

#include <cstdlib>

#include <fstream>

#include <numeric>

#include <sstream>

#include <cassert>

#include <tuple>

#include <iomanip>

#include <random>

#include <iostream>

#include <algorithm>

#include <stdio.h>



using namespace std;



#define ll long long



const unsigned long long MAXN = (int)3e5 + 5;

const int MAXI = (int)2e9;

const int K = 3;



int main(){

    ll n,sz;cin >> n >> sz;

    vector<ll> dp(MAXN, 0);

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

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

        for (ll have = sz - w;have >= 0;have --) {

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

        }

    }

    ll ans = 0;

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

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

    cout << ans;

    return 0;

}

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

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <queue>

#include <chrono>

#include <stack>

#include <string>

#include <bitset>

#include <unordered_map>

#include <cstdio>

#include <limits>

#include <vector>

#include <climits>

#include <cstring>

#include <cstdlib>

#include <fstream>

#include <numeric>

#include <sstream>

#include <cassert>

#include <tuple>

#include <iomanip>

#include <random>

#include <iostream>

#include <algorithm>

#include <stdio.h>



using namespace std;



#define ll long long



const unsigned long long MAXN = (int)3e5 + 5;

const int MAXI = (int)2e9;

const ll INF = (1e18);

const int K = 3;



int main(){

    int n,sz;cin >> n >> sz;

    vector<ll> dp(sz + 100);

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

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

        for (int have = sz - w;have >= 0;have --) {

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

        }

    }

    ll ans = 0;

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

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

    }

    cout << ans;

    return 0;

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

using namespace std;

#define ll long long int

#define MAX 100005

int n,w;

vector<int> wt(MAX);

vector<int> val(MAX);

vector<int> test(12);



void max_self(ll&a ,ll b)

{

    a = max(a,b);

}



int main()

{

    cin >> n >> w;

    

    vector<ll> dp(w+1);

    // dp[i] -> the maximum total value for weight exactly

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

    {

        int weight,value;

        cin >> weight >> value;

        for(int wt_done = w-weight;wt_done>=0;--wt_done)

        max_self(dp[wt_done+weight],dp[wt_done]+value);

    }



    ll ans = 0;

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

    max_self(ans,dp[i]);

    cout << ans;

}

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

using namespace std;



#define int long long 



void max_self(int &a, int b)

{

	a = max(a,b);

}



signed main()

{

	int n,w;

	cin >> n >> w;

	vector<int> dp(w+1); // 0...W

	// dp[i] - max total value that can be obtained with total weight exactly i

	dp[0] = 0;

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

	{

		int weight,val;

		cin >> weight >> val;

			for(int weight_added = w-weight; weight_added >= 0; --weight_added)

			max_self(dp[weight_added + weight],dp[weight_added] + val);

		

	}

	int ans = 0;

	for(auto x:dp)

	{

		max_self(ans,x);

	}

	cout << ans;

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

using namespace std;

#define ll long long int

#define MAX 100005

int n,w;

vector<int> wt(MAX);

vector<int> val(MAX);

vector<int> test(12);



void max_self(ll&a ,ll b)

{

    a = max(a,b);

}



int main()

{

    cin >> n >> w;

    

    vector<ll> dp(w+1);

    // dp[i] -> the maximum total value for weight exactly

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

    {

        int weight,value;

        cin >> weight >> value;

        for(int wt_done = w-weight;wt_done>=0;--wt_done)

        max_self(dp[wt_done+weight],dp[wt_done]+value);

    }



    ll ans = 0;

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

    max_self(ans,dp[i]);

    cout << ans;

}

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





using namespace std;



#define int long long

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

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

#define ff first 

#define ss second 

typedef vector<int> vi;

typedef pair<int,int> pii;

typedef vector<string> vs;

typedef map<int,int> mii;

typedef map<char,int> mci;

typedef vector<vector<int>> vvi;

typedef vector<pair<int,int>> vpii;

template<class T>

istream &operator>>(istream &in, vector<T> &arr){

	for(auto &x: arr) in >> x;

	return in;

}





signed main(){

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    int n,w;

    cin >> n >> w;



    vi wt(n),v(n);

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



    vvi dp(w + 1,vi(n + 1));

    dp[0][0] = 0;



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

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

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

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

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

            }

        }

    }



    cout << dp[w][n];

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

using namespace std;

#define ll long long int

#define MAX 100005

int n,w;

vector<int> wt(MAX);

vector<int> val(MAX);

vector<int> test(12);



void max_self(ll&a ,ll b)

{

    a = max(a,b);

}



int main()

{

    cin >> n >> w;

    

    vector<ll> dp(w+1);

    // dp[i] -> the maximum total value for weight exactly

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

    {

        int weight,value;

        cin >> weight >> value;

        for(int wt_done = w-weight;wt_done>=0;--wt_done)

        max_self(dp[wt_done+weight],dp[wt_done]+value);

    }



    ll ans = 0;

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

    max_self(ans,dp[i]);

    cout << ans;

}

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

using namespace std;

#define int long long

#define vvi vector<vector<int>> 

#define vi vector<int> 

#define vpii vector<pair<int,int>> 

#define ff first

#define ss second

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

#define ffor(i,n) for(int i = 0; i < n; ++i)

signed main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    int N,W;

    cin >> N >> W;

    vi wt(N),val(N);

    ffor(i,N) cin >> wt[i] >> val[i];

    // take item or not take

    // dp[i][j] -> total value for i items and total weight taken is j until now



    vvi dp(N + 1,vi(W + 1,0));

    

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

    {

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

        {

            // don't take current element

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

            // take current element if possible

            if(j - wt[i - 1] >= 0)

            {

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

            }

        }

    }

    // answer will be dp[N][W];

    cout << dp[N][W];

}