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

using namespace std;

#define ll long long int

#define mo 1000000007

#define pb emplace_back

typedef vector<ll> vi;

void solve(){

int n=0,k=0,w=0;

ll sum;

cin>>n>>w;

vi dp(w+1,0);

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

	ll u,v;

	cin>>u>>v;

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

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

	}

}

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

}

int main(){

ios::sync_with_stdio(false);

cin.tie(0);

   int t=1;

   //cin>>t;

     while(t--){

     	solve();

	 }

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

using namespace std;

#define ll long long int

#define mo 1000000007

#define pb emplace_back

typedef vector<ll> vi;

void solve(){

int n=0,k=0,w=0;

ll sum;

cin>>n>>w;

vi dp(w+1,0);

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

	ll u,v;

	cin>>u>>v;

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

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

	}

}

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

}

int main(){

ios::sync_with_stdio(false);

cin.tie(0);

   int t=1;

   //cin>>t;

     while(t--){

     	solve();

	 }

     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.7550556937680035x):
#include <iostream>

#include <vector>

using namespace std;



int main()

{

    ios::sync_with_stdio(false);

    int n,w;

    cin >> n >> w;

    vector<pair<int,int> > v(n);

    long long int ans = 0;

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

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

    vector<vector<long long int> > dp(n+1,vector<long long int>(w+1,0));

    

    // first = weight & second = value

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

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

            if(j<v[i-1].first)

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

            else

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

        }

    }

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

    

    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.2774272921008722x):
#include <iostream>

#include <vector>

using namespace std;



int main()

{

    ios::sync_with_stdio(false);

    int n,w;

    cin >> n >> w;

    vector<pair<int,int> > v(n);

    long long int ans = 0;

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

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

    vector<vector<long long int> > dp(n+1,vector<long long int>(w+1,0));

    

    // first = weight & second = value

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

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

            if(j<v[i-1].first)

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

            else

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

        }

    }

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

    

    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.757005015576409x):
#include <iostream>

#include <vector>

using namespace std;



int main()

{

    ios::sync_with_stdio(false);

    int n,w;

    cin >> n >> w;

    

    vector<pair<int,int> > v(n);

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

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

    

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

    

    // first = weight & second = value

    

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

        for(int j=w;j>=v[i].first;j--)

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

    

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

    

    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.2788461170920031x):
#include <iostream>

#include <vector>

using namespace std;



int main()

{

    ios::sync_with_stdio(false);

    int n,w;

    cin >> n >> w;

    

    vector<pair<int,int> > v(n);

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

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

    

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

    

    // first = weight & second = value

    

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

        for(int j=w;j>=v[i].first;j--)

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

    

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

    

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

using namespace std;



long long n, w, dp[110][100100], a[110], b[110];



long long solve(int i, long long c){

	

	if(i == n || c <= 0) return 0;

	

	if(dp[i][c] == -1) dp[i][c] = max(c < a[i] ? 0 : (solve(i + 1, c - a[i]) + b[i]), solve(i + 1, c));

	

	return dp[i][c];

}



int main(){

	

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

	

	for(int i = 0; i < n; i++) scanf(" %lld %lld", &a[i], &b[i]);

	

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

	

	printf("%lld\n", solve(0, w));

	

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

using namespace std;



long long n, w, dp[110][100100], a[110], b[110];



long long solve(int i, long long c){

	

	if(i == n || c <= 0) return 0;

	

	if(dp[i][c] == -1) dp[i][c] = max(c < a[i] ? 0 : (solve(i + 1, c - a[i]) + b[i]), solve(i + 1, c));

	

	return dp[i][c];

}



int main(){

	

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

	

	for(int i = 0; i < n; i++) scanf(" %lld %lld", &a[i], &b[i]);

	

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

	

	printf("%lld\n", solve(0, w));

	

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



using namespace std;



long long memo[101][100001];



long long phi(const int &n, const int &c, const int items[][2]){

    long long ans;

    if(n == 0 || c == 0) ans = 0;

    else if(memo[n][c] != -1) ans = memo[n][c];

    else if(c - items[n - 1][0] < 0) ans = phi(n - 1, c, items);

    else{

        ans = max(items[n - 1][1] + phi(n - 1, c - items[n - 1][0], items), phi(n - 1, c, items));

    }

    return memo[n][c] = ans;

}



int main(){

    int N, C;

    while(scanf("%d %d", &N, &C) != EOF){

        int items[N][2];

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

            for(int c = 0; c <= C; c++){

                memo[n][c] = -1;

            }

        }

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

            scanf("%d %d", &items[i][0], &items[i][1]);

        }

        printf("%lli\n", phi(N, C, items));

    }

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



using namespace std;



long long memo[101][100001];



long long phi(const int &n, const int &c, const int items[][2]){

    long long ans;

    if(n == 0 || c == 0) ans = 0;

    else if(memo[n][c] != -1) ans = memo[n][c];

    else if(c - items[n - 1][0] < 0) ans = phi(n - 1, c, items);

    else{

        ans = max(items[n - 1][1] + phi(n - 1, c - items[n - 1][0], items), phi(n - 1, c, items));

    }

    return memo[n][c] = ans;

}



int main(){

    int N, C;

    while(scanf("%d %d", &N, &C) != EOF){

        int items[N][2];

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

            for(int c = 0; c <= C; c++){

                memo[n][c] = -1;

            }

        }

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

            scanf("%d %d", &items[i][0], &items[i][1]);

        }

        printf("%lli\n", phi(N, C, items));

    }

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

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

#define ii          pair<int,int>

#define F           first

#define S           second

#define pb          push_back

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

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

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

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

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

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

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

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

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

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

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

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

using namespace std;

typedef long long   ll;

typedef vector<int> vi;

typedef vector<ii>  vii;

const int N = 1 * 1e5 + 5;

const ll mod = 1e9 + 7;

const double E = 1e-9;

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

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

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

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

// fflush(stdout)

// cout << flush

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

int n, W;

int w[101], v[101];

ll dp[101][N];

ll f(int i, int cost){

    if(cost < 0)

        return -1e18;

    if(i == n)

        return 0;

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

    if(ans == -1){

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

    }return ans;

}

int main(){

    //FL;

    FIN;

    cin >> n >> W;

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

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

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

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

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

            if(i == n){

                ans = 0;

                continue;

            }

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

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

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

        }

    }

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

    EjecuteTime;

    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.7759829576878623x):


#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 <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.2926593204491186x):


#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;

}