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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

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

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

		for (int j=t;j>=1;j--)

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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


#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <queue>

#include <stack>

#include <string>

#include <bitset>

#include <cstdio>

#include <limits>

#include <vector>

#include <climits>

#include <cstring>

#include <cstdlib>

#include <fstream>

#include <numeric>

#include <sstream>

#include <cassert>

#include <iomanip>

#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <fstream>

 

#define int                     long long

#define file(s)                 freopen(s".in","r",stdin); freopen(s".out","w",stdout);

#define forev(i, b, a)          for(int i = (b); i >=(a); i--)

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

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

 

using namespace std;

 

typedef long long ll;

typedef double db;

typedef long double ldb;

 

const ldb pi = 3.14159265358979323846264;

const int maxn = 2e5 + 1;

const int mod = 1e9 + 7;

    

int n, W, ans = -1;

int w[maxn], v[maxn];

int dp[101][100001];

    

main(){

    //file("");

    speed;

    cin >> n >> W;

    forn(i, 1, n){

        int num1, num2;

        cin >> num1 >> num2;

        w[i] = num1;

        v[i] = num2;

    }

    forn(i, 1, n){

        forn(j, 0, W){

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

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

            }

            else{

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

            }

        }

    }

    forn(i, 1, n){

        forn(j, 1, W){

            if(dp[i][j] > ans)ans = dp[i][j];

        }

    }

    cout << ans;

    return 0;

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

const int dir[4][2] = { -1,0,1,0,0,-1,0,1 };

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

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

	f[0] = 0;

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

		int w, v;

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

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

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



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

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


#include <bits/stdc++.h>

using namespace std;



int main() {

	int n,k;

	cin>>n>>k;

	vector<int>arr(n);

	vector<int>val(n);

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

		cin>>arr[i]>>val[i];

	}

	vector<long long>dp(k+1,0);

	dp[0]=0;

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

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

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

		}

	}

	cout<<dp[k]<<endl;

	return 0;

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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

            dp[wc+wi]=max(dp[wc+wi],dp[wc]+vi);

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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


#include <bits/stdc++.h>

using namespace std;



int main() {

	int n,k;

	cin>>n>>k;

	vector<int>arr(n);

	vector<int>val(n);

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

		cin>>arr[i]>>val[i];

	}

	vector<long long>dp(k+1,0);

	dp[0]=0;

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

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

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

		}

	}

	cout<<dp[k]<<endl;

	return 0;

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

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

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

		for (int j=t;j>=1;j--)

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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


#include <bits/stdc++.h>

using namespace std;



int main() {

	int n,k;

	cin>>n>>k;

	vector<int>arr(n);

	vector<int>val(n);

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

		cin>>arr[i]>>val[i];

	}

	vector<long long>dp(k+1,0);

	dp[0]=0;

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

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

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

		}

	}

	cout<<dp[k]<<endl;

	return 0;

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

const int dir[4][2] = { -1,0,1,0,0,-1,0,1 };

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

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

	f[0] = 0;

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

		int w, v;

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

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

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



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

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

#include<map>

#include<vector>

using namespace std;

typedef long long int ll;

vector<pair<ll,ll>>datados;

vector<vector<ll>>alm;

ll m(ll w,ll i){

    if(w<0){

        return -1e9;

    }

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

        return 0;

    }

    if(alm[w][i]!=-1){

        return alm[w][i];

    }



    alm[w][i]= max(m(w-datados[i].first,i-1)+datados[i].second,m(w,i-1));

    return alm[w][i];

}

int main(){

    ll a,b,c,d;

    cin>>a>>b;

    vector<int>ava(a,1);

    vector<ll>aux(a,-1);

    alm=vector<vector<ll>>(b+1,aux);

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

        cin>>c>>d;

        datados.push_back({c,d});

    }

    cout<<m(b,a-1)<<endl;

return 0;

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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

            dp[wc+wi]=max(dp[wc+wi],dp[wc]+vi);

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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

#include<map>

#include<vector>

using namespace std;

typedef long long int ll;

vector<pair<ll,ll>>datados;

vector<vector<ll>>alm;

ll m(ll w,ll i){

    if(w<0){

        return -1e9;

    }

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

        return 0;

    }

    if(alm[w][i]!=-1){

        return alm[w][i];

    }



    alm[w][i]= max(m(w-datados[i].first,i-1)+datados[i].second,m(w,i-1));

    return alm[w][i];

}

int main(){

    ll a,b,c,d;

    cin>>a>>b;

    vector<int>ava(a,1);

    vector<ll>aux(a,-1);

    alm=vector<vector<ll>>(b+1,aux);

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

        cin>>c>>d;

        datados.push_back({c,d});

    }

    cout<<m(b,a-1)<<endl;

return 0;

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

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

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

		for (int j=t;j>=1;j--)

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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

#include<map>

#include<vector>

using namespace std;

typedef long long int ll;

vector<pair<ll,ll>>datados;

vector<vector<ll>>alm;

ll m(ll w,ll i){

    if(w<0){

        return -1e9;

    }

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

        return 0;

    }

    if(alm[w][i]!=-1){

        return alm[w][i];

    }



    alm[w][i]= max(m(w-datados[i].first,i-1)+datados[i].second,m(w,i-1));

    return alm[w][i];

}

int main(){

    ll a,b,c,d;

    cin>>a>>b;

    vector<int>ava(a,1);

    vector<ll>aux(a,-1);

    alm=vector<vector<ll>>(b+1,aux);

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

        cin>>c>>d;

        datados.push_back({c,d});

    }

    cout<<m(b,a-1)<<endl;

return 0;

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

const int dir[4][2] = { -1,0,1,0,0,-1,0,1 };

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

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

	f[0] = 0;

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

		int w, v;

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

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

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



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

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

#include <bits/stdc++.h>

using namespace std;



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

typedef long long ll;

typedef pair<int, int> ii;

typedef vector<int> vi;

int n, s;

ll memo[101][(int) (1e5) + 2];

int w[101];

int v[101];

ll dp(int idx, int remw) {

	if (remw < 0)

		return -(1e9);

	if (idx == n)

		return 0;

	if (memo[idx][remw] != -1)

		return memo[idx][remw];

	ll take = v[idx] + dp(idx + 1, remw - w[idx]);

	ll leave = dp(idx + 1, remw);

	return memo[idx][remw] = max(take, leave);

}

int main() {

	ios::sync_with_stdio(false), cin.tie(0);

//	freopen("sort.in", "r", stdin);

//	freopen("sort.txt", "w", stdout);

	cin >> n >> s;

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

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

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

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

			memo[i][j] = -1;

	cout << dp(0, s);

	return 0;

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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

            dp[wc+wi]=max(dp[wc+wi],dp[wc]+vi);

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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

#include <bits/stdc++.h>

using namespace std;



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

typedef long long ll;

typedef pair<int, int> ii;

typedef vector<int> vi;

int n, s;

ll memo[101][(int) (1e5) + 2];

int w[101];

int v[101];

ll dp(int idx, int remw) {

	if (remw < 0)

		return -(1e9);

	if (idx == n)

		return 0;

	if (memo[idx][remw] != -1)

		return memo[idx][remw];

	ll take = v[idx] + dp(idx + 1, remw - w[idx]);

	ll leave = dp(idx + 1, remw);

	return memo[idx][remw] = max(take, leave);

}

int main() {

	ios::sync_with_stdio(false), cin.tie(0);

//	freopen("sort.in", "r", stdin);

//	freopen("sort.txt", "w", stdout);

	cin >> n >> s;

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

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

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

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

			memo[i][j] = -1;

	cout << dp(0, s);

	return 0;

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

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

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

		for (int j=t;j>=1;j--)

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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

#include <bits/stdc++.h>

using namespace std;



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

typedef long long ll;

typedef pair<int, int> ii;

typedef vector<int> vi;

int n, s;

ll memo[101][(int) (1e5) + 2];

int w[101];

int v[101];

ll dp(int idx, int remw) {

	if (remw < 0)

		return -(1e9);

	if (idx == n)

		return 0;

	if (memo[idx][remw] != -1)

		return memo[idx][remw];

	ll take = v[idx] + dp(idx + 1, remw - w[idx]);

	ll leave = dp(idx + 1, remw);

	return memo[idx][remw] = max(take, leave);

}

int main() {

	ios::sync_with_stdio(false), cin.tie(0);

//	freopen("sort.in", "r", stdin);

//	freopen("sort.txt", "w", stdout);

	cin >> n >> s;

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

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

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

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

			memo[i][j] = -1;

	cout << dp(0, s);

	return 0;

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

using namespace std;

typedef long long ll;



ll dp[100005];



int main(){

    ll n,w;

    cin>>n>>w;

    ll wi,vi;

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

        cin>>wi>>vi;

        for(ll wc=w-wi;wc>=0;wc--){

            dp[wc+wi]=max(dp[wc+wi],dp[wc]+vi);

        }

    }

    ll ans=0;

    for(auto i:dp) ans=max(ans,i);

    cout<<ans;



    return 0;

}


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

#include <vector>

#include <string>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <unordered_map>

#include <unordered_set>

#include <cmath>

#include <algorithm>

#include <bitset>  

using namespace std;



//======================================================

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

#define for2(i,n)  for (int i = 1; i <=(int)(n); ++i)

#define forr1(i,n)  for (int i = n - 1 ;i <= 0; --i)

#define forr2(i,n)  for (int i = n  ;i < 0; --i)

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

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

#define clr(v,d)   memset(v, d, sizeof(v))

#define ull        unsigned long long

#define MP(a,b)	   make_pair(a,b)

#define S          second

#define F          first

#define PI         3.14159265359

#define ll         long long

#define sz(v)	   v.size()

#define pb         push_back

#define pp         pop_back

#define bgn        begin

#define N          100000+5

#define	MOD        1e9+7

#define inf        1e18

//======================================================

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

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

//======================================================

ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }

ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }

ll power(ull a, ull b, ull ret = 1LL) {

	while (b--) ret = (ret * a);

	return ret;

}

//======================================================







int weights[100+9];

long long benefit[100+9];

int n , kpWeight;

long long dp[100 + 9][100000 + 9];



long long  knapSack(int index , int reminderWeight)

{

	if (index == n)

		return 0;



	if (dp[index][reminderWeight] != -1)

	{

		return dp[index][reminderWeight];

	}



	long long leave = knapSack(index + 1, reminderWeight);



	long long take = 0;

	if (reminderWeight >= weights[index])

	{

		take = benefit[index] + knapSack(index + 1, reminderWeight - weights[index]);

	}

	return dp[index][reminderWeight] = max(leave, take);

}



int main()

{

	

	cin >> n >> kpWeight;

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

	{

		int a;

		long long b;

		cin >> a >> b;

		weights[i] = a;

		benefit[i] = b;

	}

	for (int i1 = n - 1; i1 >= 0; i1--)

	{

		for (int i2 = 0; i2 <= kpWeight; i2++)

		{

			if (i2 >= weights[i1])

			{

				dp[i1][i2] = max(benefit[i1] + dp[i1 + 1][i2 - weights[i1]], dp[i1 + 1][i2]);



			}

			else

			{

				dp[i1][i2] = dp[i1 + 1][i2];



			}

		}

	}

	cout << dp[0][kpWeight];

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



using namespace std;

typedef long long ll;

typedef unsigned long long ull;



const int mod  = 100003;

const int maxn = 1e5+10;



struct yao

{

	ll val,tim;

};

ll dp[maxn];

yao p[110];

int main()

{

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

	int t,m;

	cin>>m>>t;

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

		cin>>p[i].tim>>p[i].val;

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

	{

		for (int j=t;j>=1;j--)

		{

			if (j>=p[i].tim)

				dp[j]=max(dp[j],dp[j-p[i].tim]+p[i].val);

		}

	}

	cout<<dp[t];

    return 0;

}


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

#include <vector>

#include <string>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <unordered_map>

#include <unordered_set>

#include <cmath>

#include <algorithm>

#include <bitset>  

using namespace std;



//======================================================

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

#define for2(i,n)  for (int i = 1; i <=(int)(n); ++i)

#define forr1(i,n)  for (int i = n - 1 ;i <= 0; --i)

#define forr2(i,n)  for (int i = n  ;i < 0; --i)

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

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

#define clr(v,d)   memset(v, d, sizeof(v))

#define ull        unsigned long long

#define MP(a,b)	   make_pair(a,b)

#define S          second

#define F          first

#define PI         3.14159265359

#define ll         long long

#define sz(v)	   v.size()

#define pb         push_back

#define pp         pop_back

#define bgn        begin

#define N          100000+5

#define	MOD        1e9+7

#define inf        1e18

//======================================================

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

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

//======================================================

ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }

ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }

ll power(ull a, ull b, ull ret = 1LL) {

	while (b--) ret = (ret * a);

	return ret;

}

//======================================================







int weights[100+9];

long long benefit[100+9];

int n , kpWeight;

long long dp[100 + 9][100000 + 9];



long long  knapSack(int index , int reminderWeight)

{

	if (index == n)

		return 0;



	if (dp[index][reminderWeight] != -1)

	{

		return dp[index][reminderWeight];

	}



	long long leave = knapSack(index + 1, reminderWeight);



	long long take = 0;

	if (reminderWeight >= weights[index])

	{

		take = benefit[index] + knapSack(index + 1, reminderWeight - weights[index]);

	}

	return dp[index][reminderWeight] = max(leave, take);

}



int main()

{

	

	cin >> n >> kpWeight;

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

	{

		int a;

		long long b;

		cin >> a >> b;

		weights[i] = a;

		benefit[i] = b;

	}

	for (int i1 = n - 1; i1 >= 0; i1--)

	{

		for (int i2 = 0; i2 <= kpWeight; i2++)

		{

			if (i2 >= weights[i1])

			{

				dp[i1][i2] = max(benefit[i1] + dp[i1 + 1][i2 - weights[i1]], dp[i1 + 1][i2]);



			}

			else

			{

				dp[i1][i2] = dp[i1 + 1][i2];



			}

		}

	}

	cout << dp[0][kpWeight];

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

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

const int dir[4][2] = { -1,0,1,0,0,-1,0,1 };

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };











const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

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

	f[0] = 0;

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

		int w, v;

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

		for (int i = C; i >= w; i--)if(f[i-w]!=-1) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= C; i++)ans = max(ans, f[i]);

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



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}

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



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

#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

#define trav(a,x) for (auto& a: x)

#define cout(tt) cout<<"Case #"<<(tt)<<": ";

#define minheap(name) priority_queue <int, vector<int>, greater<int> > (name); 

#define ll long long int

/*	Things to remember handling:

	1. int overflows

	2. array boundaries

	3. base cases (n=1)

*/



using namespace std;



int main(){

	ios::sync_with_stdio(0);

	cin.tie(0);

	

		int W,N;

		cin>>N>>W;

		int v[N],w[N];

		FOR(i,0,N){

			cin>>w[i];

			cin>>v[i];

		}

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

		FOR(i,1,N+1){

			FOR(j,1,W+1){

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

					int newWeight = j-w[i-1];

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

				}else

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

			}

		}

		cout<<dp[N][W]<<endl;

			

	

}