stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <cstring>

#include <vector>

#include <algorithm>

#include <cmath>

#include <string>

#include <set>

#include <utility>

#include <cstdlib>

#include <queue>

#include <stack>

#include <iomanip>

#include <cstdio>

#include <map>



using namespace std;



using ll = long long;

using P = pair<ll,ll>;



#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)

#define rrep(i,x) for(ll i = ((ll)(x) - 1); i >= 0; i--)



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

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

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );



template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}

template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}



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

//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}



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

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



const ll mod = 1e9 + 7;

const ll IMF = 1e18;

const double PI = 3.14159265358979323846;





// ****************************************CODE***************************************//







ll n,W;

ll w[110],v[110];

ll dp[100010];



int main(){

        cin >> n >> W;

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

        for(int i = 0; i < 100005; i++) dp[i] = -IMF;

        dp[0] = 0;

        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]);

                }

        }



        ll ans = 0;

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

        cout << ans << endl;

        return 0;

}










































































































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

#include <string>

#include <cstring>

#include <vector>

#include <algorithm>

#include <cmath>

#include <set>

#include <utility>

#include <cstdlib>

#include <queue>

#include <stack>

#include <iomanip>

#include <cstdio>

#include <map>

#include <list>

#include <stdio.h>

#include <sstream>

using namespace std;

using ll = long long;

using P = pair<ll,ll>;

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

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

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

//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}

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

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

const ll mod = 1e9 + 7;

const ll inf = 1LL << 60;

const long double pi = 3.14159265358979323846;



// ****************************************CODE***************************************//



ll n, w, weight[110], value[110], dp[110][100100];



int main() {

    cin >> n >> w;

    for(int i = 0; i < n; i++) cin >> weight[i] >> value[i];



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

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

            if(j - weight[i] >= 0) dp[i+1][j] = max(dp[i+1][j], dp[i][j - weight[i]] + value[i]);

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

        }

    }



    cout << dp[n][w] << endl;

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

using namespace std;

using i64 = int64_t;

using vi = vector<i64>;

using vvi = vector<vi>;



i64 dp[101][101010];



int main() {

    int n, W;

    cin >> n >> W;



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

        int v, w;

        cin >> w >> v;

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

            if (j - w >= 0) {

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

            } else {

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

            }

        }

    }

    i64 ans = 0;

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

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

    }

    cout << ans << endl;

}


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

using namespace std;

using i64 = int64_t;

using vi = vector<i64>;

using vvi = vector<vi>;



i64 solve_knapsack_small_weight(const vi &ws, const vi &vs, int MAX_WEIGHT) {

    int n = ws.size();

    vi value(MAX_WEIGHT + 1);

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

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

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

                value[j] = max(value[j], value[j - ws[i]] + vs[i]);

            }

        }

    }

    i64 nax = 0;

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

        nax = max(nax, value[i]);

    }

    return nax;

}



int main() {

    int n, w;

    cin >> n >> w;

    vi ws(n), vs(n);

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

        cin >> ws[i] >> vs[i];

    }

    cout << solve_knapsack_small_weight(ws, vs, w) << endl;

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

#define rep(i, m, n) for(int i = m; i < (n); i++)

#define rrep(i,m,n) for(int i = m; i >= n; i--)

#define print(x) cout << (x) << endl;

#define print2(x,y) cout << (x) << " " << (y) << endl;

#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;

#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}

#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;

#define INF (1e18)

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

typedef struct{

    ll to;

    ll cost;

} edge;

typedef pair<ll, ll> lpair;

ll dp[110][100010] = {};



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N,W;

    ll w[110], v[110];

    cin >> N >> W;

    rep(i,0,N) cin >> w[i] >> v[i];

    ll dp[100010] = {};

    rep(i,0,N){

        rrep(j,W, w[i]){

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

        }

    }

    print(dp[W]);

    // ll N,W;

    // ll w[110], v[110];

    // cin >> N >> W;

    // rep(i,0,N){

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

    // }

    // rep(i,0,N){

    //     rep(j,0,W+1){

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

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

    //         }else{

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

    //         }

    //     }

    // }

    // print(dp[N][W]);

}


// Faster C++ solution for the same problem (measured speedup: 1.7950634870349131x):
/*** author: yuji9511 ***/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using lpair = pair<ll, ll>;

const ll MOD = 1e9+7;

const ll INF = 1e18;

#define rep(i,m,n) for(ll i=(m);i<(n);i++)

#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)

#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};

void print() {}

template <class H,class... T>

void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}

ll dp[110][100010] = {};



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N,W;

    cin >> N >> W;

    ll w[110], v[110];

    rep(i,0,N) cin >> w[i] >> v[i];

    dp[0][0] = 0;

    rep(i,0,N){

        rep(j,0,W+1){

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

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

            }

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

        }

    }

    print(dp[N][W]);





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

using namespace std;

#define M 1000000007

#define U 998244353

#define N 1300005

#define int long long

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

#define fr first

#define ll long long 

#define sc second

#define pb push_back

#define mp make_pair

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

#define rep(i,a,n) for(int i=a ; i<n ; i++)

#define r0 return 0;

#define endl '\n'

#define INF (int)1e15

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1){

    std::cerr << name << " : " << arg1 << endl;

}

template <typename Arg1, typename... Args>

void __f(const char* names, Arg1&& arg1, Args&&... args){

    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);

}

int power(int x, unsigned int y, unsigned int m)

{

    if (y == 0)

        return 1;

    int p = power(x, y/2, m) % m;

    p = (p * p) % m;

    return (y%2 == 0)? p : (x * p) % m;

}

        int dp[100001];

signed main()

{

    ios_base::sync_with_stdio(0);

    int TESTS=1;

    // cin>>TESTS;

    while(TESTS--)

    {   

        int n,w;

        cin>>n>>w;

        pair<int,int> a[n];

        rep(i,0,n){

            int b,c;

            cin>>b>>c;

            a[i] = {b,c};

        }

        dp[0] = 0;

        rep(i,1,100001) dp[i] = -INF;

        rep(i,0,n){

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

                if(dp[j]!=-INF){

                    if(a[i].fr+j>w) continue;

                    dp[a[i].fr+j] = max(dp[a[i].fr+j], dp[j]+a[i].sc);

                }

            }

        }

        int ans=-INF;

        rep(i,0,w+1) ans = max(ans,dp[i]);

        cout<<ans;

    }       

}     

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

using namespace std;

#define M 1000000007

#define U 998244353

#define N 1000005

#define int long long

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

#define fr first

#define ll long long 

#define sc second

#define pb push_back

#define mp make_pair

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

#define rep(i,a,n) for(int i=a ; i<n ; i++)

#define r0 return 0;

#define endl '\n'

#define INF (int)1e15

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1){

	std::cerr << name << " : " << arg1 << endl;

}

template <typename Arg1, typename... Args>

void __f(const char* names, Arg1&& arg1, Args&&... args){

	const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);

}

signed main()

{

	ios_base::sync_with_stdio(0);

	int TESTS=1;

	// cin>>TESTS;

	while(TESTS--)

	{   

		int n,w;

		cin >> n >> w;

		int val[w+1]={};

		rep(i,0,w+1) val[i] = -1;

		val[0] = 0;

		rep(i,0,n){

			int t;

			cin >> t;

			int r;;

			cin >> r;

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

				if(j+t<=w && val[j]!=-1){

					val[j+t] = max(val[j+t], val[j]+r);

				}

			}

		}

		int mx = -INF;

		rep(j,0,w+1) mx = max(mx, val[j]);

		cout<<mx;

	}

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

#include<math.h>

#include<algorithm>



#define long long long



using namespace std;



long n, m;

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



long cal(int idx, int weight) {

    if (idx > n) return 0;

    if (dp[idx][weight] != -1) return dp[idx][weight];

    dp[idx][weight] = 0;



    if (weight + w[idx] <= m) dp[idx][weight] = max(cal(idx + 1, weight), cal(idx + 1, weight + w[idx]) + v[idx]);

    else dp[idx][weight] = dp[idx][weight] = cal(idx + 1, weight);

    return dp[idx][weight];

}



void FastInput()

{

    ios_base::sync_with_stdio(NULL);

    cin.tie(NULL);

    cout.tie(NULL);

}



void Input()

{

    cin >> n >> m;

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

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

        for (int j = 0; j <= 100000; j ++) dp[i][j] = -1;

}



void Solve()

{

    cout << cal(1,0);

}



int main()

{

    FastInput();

    Input();

    Solve();

}




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

#include<algorithm>

#include<math.h>

#include<cstring>

#include<vector>



using namespace std;



#define long long long

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

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



const int MAXN = 1e5 + 5;

const long oo = 1e15;



long ans , n , m;

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



void Solve() {

    ft(i , 1 , n) {

        fd(j , m , w[i]) {

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

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

        }

    }

    cout << ans;

}



void FastInput() {

    ios_base::sync_with_stdio(NULL);

    cin.tie(NULL);

    cout.tie(NULL);

    //freopen(".inp", "r", stdin);

    //freopen(".out", "w", stdout);

}



void Input() {

    cin >> n >> m;

    ft(i , 1 , n) cin >> w[i] >> v[i];

}



int main() {

    FastInput();

    Input();

    Solve();

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



using namespace std;



#define REP(i,a,b) for(ll i = a; i < b; i++)

#define DB( x ) cout << #x << " = " << x << endl;

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

#define endl '\n'



typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll, ll> pii;

typedef pair<int, pii> tri;

typedef vector <vector <ll>> matrix;

typedef pair<string, string> pss;



const ll mod = (ll)1e9 + 7;

const int MAX = (int)1e6 + 100;



const int oo = 0x3f3f3f3f;



ll dp[MAX];



void knapsack(vector<pii> &v, int max_w){



    ll solve = 0;



    for(int i = 0;i < sz(v);++i){

        for(int j = max_w; j >= 1;--j){

            if(j - v[i].first >= 0){

                dp[j] = max(dp[j], dp[j - v[i].first] + v[i].second);

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

            }

        }

    }



    cout << solve << endl;

}



int main() {

    ios_base::sync_with_stdio(0);

    cin.tie(0);



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



    vector<pii> v(n);



    for(auto &it : v)

        cin >> it.first >> it.second;



    knapsack(v, 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.621174207634154x):
#include<iostream>

#include<algorithm>

using namespace std;

int v[105],w[105];

long long dp[100005];



int main()

{

	int n,W;

	cin>>n>>W;

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

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

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

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

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

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

	long long ans=-1;

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

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

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



using namespace std;



long long n, W, v[107], w[107], dp[107][100007];



int main() {

	cin >> n >> W;

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

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

	}

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

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

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

			if ( j >= w[i] ) {

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

			}

		}

	}

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

#include <cstdio>

using namespace std;

const int N = 110, M = 101000;

long long n, m, f[M], a[N], v[N]; 

int main(){

	scanf("%lld%lld", &n, &m);

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

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

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

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

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

	printf("%lld\n", f[m]);

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

using namespace std;

typedef long long ll;

const int MX = 1e5 + 5;





int main()

{

    ll n,w;

    cin>>n>>w;

    vector<ll> value(n),weight(n);

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

    {

        cin>>weight[i]>>value[i];

    }

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

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

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

   {

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

       {

        if(j>=weight[i])

            dp[i+1][j]=max(dp[i][j],dp[i][j-weight[i]]+value[i]);

        else

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

    }



   }



    cout<<dp[n][w]<<endl;

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



ll n, a[maxn], w[maxn], s;

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

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

			if (dp[j] != -1)

				dp[j + w] = max(dp[j + w], dp[j] + cost);

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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

using namespace std;



int main()

{

    long long weight,cost,n,capacity;

    cin>>n>>capacity;

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

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

    {

        cin>>weight>>cost;

        for(int b=capacity;b>=weight;b--)

        {

            dp[b]=max(dp[b],dp[b-weight]+cost);

        }

    }

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

using namespace std;

long long n,i,w,a,b,k[101][100001],j;

main()

{

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

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

    {

        scanf("%lld %lld",&a,&b);

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

        {

            if(j<a) k[i][j]=k[i-1][j];

            else k[i][j]=max(k[i-1][j],k[i-1][j-a]+b);

        }

    }

    printf("%lld ",k[n][w]);

}