stablegradients/pie-gem5-pairs huggingface dataset:
// 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.6544002561737274x):
#include<bits/stdc++.h>



using namespace std;



long long mem[100005][2];



int a[105];

int b[105];



int main()

{

    int n,k;

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

    int i;

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

    {

        scanf("%d %d",&a[i],&b[i]);

    }

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

    {

        mem[i][0] = -1e9;

        mem[i][1] = -1e9;

    }

    mem[0][0] = 0;

    mem[0][1] = 0;

    bool flag = 0;

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

    {

        flag = !flag;

        int j;

        for(j=0;j<=k;j++)

        {

            if(j-a[i]>=0)mem[j][flag] = max(mem[j][!flag],mem[j-a[i]][!flag] + b[i]);

            else mem[j][flag] = mem[j][!flag];

        }

    }

    long long ans = 0;

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

    {

        ans = max(mem[i][flag],ans);

    }

    printf("%lld",ans);

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



using namespace std;

int N,W;

int w[100];

long long v[100];



long long knap(int n,int u){

    double K[n+1][u+1];

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

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

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

                K[i][j] = 0;

            }

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

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

            else

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

            //cout<< K[i][j] << " ";

        }

        //cout << endl;

    }

    return K[n][u];

}



int main(){

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

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

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

    }

    long long x = knap(N,W);

    printf("%.0lld",x);

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

long long int j[100001];

long long int k[100001];

int main() {

	int n, w;

	std::cin >> n >> w;

	int x, y;

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

		std::cin >> x >> y;

		for (int e = x; e <= w; e++) {

			if (k[e - x] + y > k[e])

				j[e] = k[e - x] + y;

			else

				j[e] = k[e];

		}

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

			k[e] = j[e];

		}

	}

	std::cout << j[w];

	

	return 0;

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



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

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

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

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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

using namespace std;



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

template <typename Arg1>

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

  cerr << name << " : " << arg1 << "\n";

}

template <typename Arg1, typename... Args>

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

  const char* c = strchr(na + 1, ',');

  cerr.write(na, c - na) << " : " << arg1 << " , ";

  __f(c + 1, args...);

}

#define endl "\n"

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

#define UNIQUE(v) sort(all(v)),v.erase(unique(all(v)),v.end())

typedef long long LL;

typedef pair <int,int> pii;

const double pi = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9 + 7;

const int inf = 1e9;

const LL INF = 1e18;

const int N = 1e5 + 5;



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(0); cout.tie(0);

  #ifdef LOCAL

    freopen("input.txt", "r", stdin);

  #endif // LOCAL

  int n, cap;

  cin >> n >> cap;

  vector <LL> w (n + 1);

  vector <LL> v (n + 1);

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

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

  }

  vector <vector <LL> > dp (n + 5, vector <LL> (cap + 5, 0));

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

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

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

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

    }

  }

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

#include <bits/stdc++.h>

#define mod 998244353

typedef long long ll;



using namespace std;



void Fastio(){

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

}



ll fact[1000006], inv[1000006];



ll fp(ll base, ll exp)

{

    if (exp == 0)

        return 1;

    ll ans = fp(base, exp / 2);

    ans = (ans * ans) % mod;

    if (exp % 2 != 0)

        ans = (ans * (base % mod)) % mod;

    return ans;

}



void calcFacAndInv(ll n)

{

    fact[0] = inv[0] = 1;

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

    {

        fact[i] = (i * fact[i - 1]) ;

        inv[i] = fp(fact[i], mod - 2);

    }

}



ll ncr(ll n, ll r)

{

    return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;

}



ll npr(ll n, ll r)

{

    return (fact[n] * inv[n - r]) % mod;

}



long double  NCR(int n, int m){

    long double res = 1;

    m = min(m, n - m);

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

        res = res * ( n - i) / (i + 1);

 }

    return res;

}

ll tol(string a){

    ll res=0;

    while(a[0]=='0'){

        a.erase(a.begin());

    }

    if(a=="")a="0";

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

        res*=10; res+=a[i]-'0';

    }

    return res;

}

int check(string a, string b){

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

        if(a[i]>b[i])return 1;

        if(b[i]>a[i])return -1;

    }

    return 0;

}

class data{

public:

    ll v,d,p;

    data(){}

    data(ll vv, ll dd, ll pp){

        v=vv;  d=dd; p=pp;

    }

};



int primeFactors(int n)

{

    ll c=0;

    while (n % 2 == 0)

    {

        c++;

        n = n/2;

    }

    for (int i = 3; i*i <= n; i = i + 2)

    {

        while (n % i == 0)

        {

            c++;

            n = n/i;

        }

    }

    if (n > 2)

        c++;

    return c;

}



int main()

{

    Fastio();

    ll n,x; cin>>n>>x;

    ll w[n+1]={0},p[n+1]={0};

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

        cin>>w[i]>>p[i];

    }

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

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

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

        for(int y=0; y<=x; y++){

            if(w[i]<=y)dp[i][y]=max(dp[i-1][y], dp[i-1][y-w[i]]+p[i]);

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

        }

    }

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



    return 0;

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



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

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

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

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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

#include <algorithm>

#define ll long long



using namespace std;



ll dp[105][100005];



int main()

{

    ll n,w;

    //weight,value

    pair<ll,ll>arr[105];

    cin>>n>>w;

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

        cin>>arr[i].first>>arr[i].second;

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

    {

        if(i>=arr[0].first)

            dp[0][i]=arr[0].second;

    }

    // outer loop on rows --> items

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

    {

        // inner loop on columns --> weights

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

        {

            if(j<arr[i].first)

            {

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

            }

            else

            {

                //          not taken  , taken

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

            }

        }

    }

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

    return 0;

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



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

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

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

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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

#define ll long long

using namespace std;



int main()

{

    ll n,w;

    cin>>n>>w;

    ll weight[n+5],value[n+5];

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

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

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

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

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

            dp[i][j]=1e10;*/

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

        dp[i][0]=0;

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

        dp[0][i]=0;

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

    {

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

        {

            if(weight[i]>j)

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

            else

            {

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

            }

        }

    }

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

    {

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

        {

            cout << dp[i][j]<<" " ;

        }

        cout << endl;

    }*/

    cout << dp[n][w];



    return 0;

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



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

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

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

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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



using namespace std;

const int N = 1e5 + 5;

long long weigh[N], val[N], dp[105][N];



int main()

{

	int n, w;

	cin >> n >> w;

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

		cin >> weigh[i] >> val[i];

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

	{

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

		{

			long long op1, op2=0;

			op1 = dp[it - 1][rem];

			if (rem >= weigh[it])

				op2 = val[it] + dp[it - 1][rem - weigh[it]];

			dp[it][rem] = max(op1, op2);

		}

	}

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



	return 0;

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



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

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

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

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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



using namespace std;

using ll = long long;



#define F 	first

#define S 	second





int main() {

	int N, W;

	int w[110], v[110];

	ll dp[2][100010];

	int curr = 0, prev = 1;



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

	for (int i = 0; i < N; i++) cin >> w[i] >> v[i];



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

		dp[curr][i] = i >= w[0]? v[0] : 0;



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

		swap(curr, prev);

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

			dp[curr][j] = j < w[i]? dp[prev][j] : max(dp[prev][j], 

									dp[prev][j - w[i]] + (ll) v[i]);

		}

	}



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

	return 0;

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

#include <stdio.h>

#include <cmath>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define ll long long



using namespace std;



const int inf = 1e9 + 5;

const ll INF = 1e18 + 5;

const int maxn = 2e5 + 5;



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

ll dp[maxn];



int main(){

    cin.tie(0);

    cout.tie(0);

    ios_base::sync_with_stdio(NULL);

	cin >> n >> s;

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

	dp[0] = 0;

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

		int w, cost;

		cin >> w >> cost;

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

			if (dp[j] != -1)

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

		}

	}

	ll ans = -1;

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

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

	cout << ans;

	return 0;

}

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

using namespace std;



int n, w;

long long wei[101], val[101], dp[101][100001];



int main(){

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

	for (int i=1; i<=n; i++) scanf("%lld %lld", &wei[i], &val[i]);

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

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

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

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

		}

	}

	printf("%lld\n", 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.5866573788283045x):
#include<bits/stdc++.h>

using namespace std;



unsigned long long knapsack(vector<unsigned long long>&weight,vector<unsigned long long>&value,int n,int W)

{   vector<vector<unsigned long long>>dp(n+1,vector<unsigned long long>(W+1,0));

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

    {

      for(unsigned long long w = 1;w<=W;w++)

      {   if(w>=weight[i-1])

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

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

      }

         

    }

    return dp[weight.size()][W];

}

int main()

{

     int n,W;

  cin>>n>>W;

  vector<unsigned long long>weight(n),value(n);

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

  {

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

  }

  cout<<knapsack(weight,value,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.5894740705520296x):
#include<bits/stdc++.h>

#define ll long long

#define pii pair<int,int>

#define pll pair<ll,ll>

#define vi vector<int>

#define x first

#define y second

#define pb push_back

#define mk make_pair

#define reset(N) memset(N,0,sizeof(N))

#define clear(N) while(N.size()>0) N.pop()

#define f(a,v,b) for(int a=v;a<b;a++)

#define cb(N) __builtin_popcount(N)

#define cbl(N) __builtin_popcountl(N)

#define cbll(N) __builtin_popcountll(N)

using namespace std;

int n,w;

int we[101],va[101];

ll dp[101][100001];

void solve(){

	cin>>n>>w;

	f(i,1,n+1){

		cin>>we[i]>>va[i];

	}

	f(i,1,n+1) f(j,1,w+1){

		if(j>=we[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-we[i]]+va[i]);

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

	}

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

}

int main(){

	ios::sync_with_stdio(false);

	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: 1.454002826943167x):
#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;

}