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

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



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

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

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

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[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: 2.2671836812997768x):
#include <bits/stdc++.h>



using namespace std;

#define el '\n'

#define ll long long

typedef vector<int> vi;



int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    int n, s;

    cin >> n >> s;

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

    int a, b;

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

        cin >> a >> b;

        items[i].first = a;

        items[i].second = b;

    }

    ll dp[2][s + 1];

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

    for (int indx = n - 1; indx >= 0; --indx) {

        for (int rem = 0; rem < s + 1; ++rem) {

            ll leave = dp[1][rem];

            ll take = 0;

            if ((rem - items[indx].first) < 0)

                take = 0;

            else

                take = items[indx].second + dp[1][rem - items[indx].first];

            dp[0][rem] = max(leave, take);

        }

        for (int r = 0; r < s + 1; ++r) {

            dp[1][r] = dp[0][r];

        }

    }

    cout << dp[1][s] << el;

    return 0;

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

#define ll long long

using namespace std;

#define inf 0x3f3f3f3f 

int main(){

	ll  n , W; cin >> n >> W;

    ll w[101] , v[101] , dp[100001] = {0};

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

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

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

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

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



    cout<< dp[W] <<endl;

}

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



using namespace std;

#define el '\n'

#define ll long long

typedef vector<int> vi;



int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    int n, s;

    cin >> n >> s;

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

    int a, b;

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

        cin >> a >> b;

        items[i].first = a;

        items[i].second = b;

    }

    ll dp[2][s + 1];

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

    for (int indx = n - 1; indx >= 0; --indx) {

        for (int rem = 0; rem < s + 1; ++rem) {

            ll leave = dp[1][rem];

            ll take = 0;

            if ((rem - items[indx].first) < 0)

                take = 0;

            else

                take = items[indx].second + dp[1][rem - items[indx].first];

            dp[0][rem] = max(leave, take);

        }

        for (int r = 0; r < s + 1; ++r) {

            dp[1][r] = dp[0][r];

        }

    }

    cout << dp[1][s] << el;

    return 0;

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

using namespace std;

typedef long long ll;





ll w[105],f[100005];

ll v[105];



signed main()

{

	ll N,W;

	while(cin>>N>>W){

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

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

		

		//01背包 

		memset(f,0,sizeof f);

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

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

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

		}	

		

		cout<<f[W]<<endl;

	}

}

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



using namespace std;

#define el '\n'

#define ll long long

typedef vector<int> vi;



int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    int n, s;

    cin >> n >> s;

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

    int a, b;

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

        cin >> a >> b;

        items[i].first = a;

        items[i].second = b;

    }

    ll dp[2][s + 1];

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

    for (int indx = n - 1; indx >= 0; --indx) {

        for (int rem = 0; rem < s + 1; ++rem) {

            ll leave = dp[1][rem];

            ll take = 0;

            if ((rem - items[indx].first) < 0)

                take = 0;

            else

                take = items[indx].second + dp[1][rem - items[indx].first];

            dp[0][rem] = max(leave, take);

        }

        for (int r = 0; r < s + 1; ++r) {

            dp[1][r] = dp[0][r];

        }

    }

    cout << dp[1][s] << el;

    return 0;

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

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



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

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

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

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[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: 2.2945149747236027x):
#include <bits/stdc++.h>



using namespace std;



int main() {

    int N, W;

    cin >> N >> W;



    vector<int> w(N), v(N);

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



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



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

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

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

                dp[i][j] =

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

            else

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

        }

    }



    cout << dp[N][W];



    return 0;

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

#define ll long long

using namespace std;

#define inf 0x3f3f3f3f 

int main(){

	ll  n , W; cin >> n >> W;

    ll w[101] , v[101] , dp[100001] = {0};

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

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

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

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

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



    cout<< dp[W] <<endl;

}

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



using namespace std;



int main() {

    int N, W;

    cin >> N >> W;



    vector<int> w(N), v(N);

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



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



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

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

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

                dp[i][j] =

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

            else

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

        }

    }



    cout << dp[N][W];



    return 0;

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

using namespace std;

typedef long long ll;





ll w[105],f[100005];

ll v[105];



signed main()

{

	ll N,W;

	while(cin>>N>>W){

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

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

		

		//01背包 

		memset(f,0,sizeof f);

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

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

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

		}	

		

		cout<<f[W]<<endl;

	}

}

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



using namespace std;



int main() {

    int N, W;

    cin >> N >> W;



    vector<int> w(N), v(N);

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



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



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

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

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

                dp[i][j] =

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

            else

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

        }

    }



    cout << dp[N][W];



    return 0;

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

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



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

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

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

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[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: 2.2898897549468953x):
//D

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5+10;

ll f[maxn];

int w[105],v[105];

signed main(){

	ios::sync_with_stdio(0);

	cin.tie(0);

	int n,W;

	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 = W;j >= 0;j--)if(j >= w[i])f[j] = max(f[j],f[j - w[i]] + v[i]);

	}

	cout << f[W];

	return 0;

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

#define ll long long

using namespace std;

#define inf 0x3f3f3f3f 

int main(){

	ll  n , W; cin >> n >> W;

    ll w[101] , v[101] , dp[100001] = {0};

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

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

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

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

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



    cout<< dp[W] <<endl;

}

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5+10;

ll f[maxn];

int w[105],v[105];

signed main(){

	ios::sync_with_stdio(0);

	cin.tie(0);

	int n,W;

	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 = W;j >= 0;j--)if(j >= w[i])f[j] = max(f[j],f[j - w[i]] + v[i]);

	}

	cout << f[W];

	return 0;

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

using namespace std;

typedef long long ll;





ll w[105],f[100005];

ll v[105];



signed main()

{

	ll N,W;

	while(cin>>N>>W){

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

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

		

		//01背包 

		memset(f,0,sizeof f);

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

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

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

		}	

		

		cout<<f[W]<<endl;

	}

}

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5+10;

ll f[maxn];

int w[105],v[105];

signed main(){

	ios::sync_with_stdio(0);

	cin.tie(0);

	int n,W;

	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 = W;j >= 0;j--)if(j >= w[i])f[j] = max(f[j],f[j - w[i]] + v[i]);

	}

	cout << f[W];

	return 0;

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

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



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

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

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

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[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: 2.2987085172470163x):
#include <bits/stdc++.h>

using namespace std;

 

#define int long long int

#define ld long double

#define ll long long

#define pb push_back

#define F first

#define S second

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

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

 

typedef vector<ll> vi;

typedef pair<ll,ll> pii;

typedef vector<pii> vpii;

typedef vector<vi> vvi;

typedef map<ll,ll> mii;

typedef map<char,ll> mci;

 

ll gcd(ll a, ll b){

	if(b==0)return a;

	else return gcd(b, a%b);

}



signed main(){

    ll test=1;

    // cin>>test;

    while(test--){

        ll n, w; cin>>n>>w;

       long long  wt[10000], val[10000];

        rep(i, 0, n)cin>>wt[i]>>val[i];

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

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

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

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

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

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

        	}

        }

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

 

    }    

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

#define ll long long

using namespace std;

#define inf 0x3f3f3f3f 

int main(){

	ll  n , W; cin >> n >> W;

    ll w[101] , v[101] , dp[100001] = {0};

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

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

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

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

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



    cout<< dp[W] <<endl;

}

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

using namespace std;

 

#define int long long int

#define ld long double

#define ll long long

#define pb push_back

#define F first

#define S second

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

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

 

typedef vector<ll> vi;

typedef pair<ll,ll> pii;

typedef vector<pii> vpii;

typedef vector<vi> vvi;

typedef map<ll,ll> mii;

typedef map<char,ll> mci;

 

ll gcd(ll a, ll b){

	if(b==0)return a;

	else return gcd(b, a%b);

}



signed main(){

    ll test=1;

    // cin>>test;

    while(test--){

        ll n, w; cin>>n>>w;

       long long  wt[10000], val[10000];

        rep(i, 0, n)cin>>wt[i]>>val[i];

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

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

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

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

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

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

        	}

        }

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

 

    }    

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

using namespace std;

typedef long long ll;





ll w[105],f[100005];

ll v[105];



signed main()

{

	ll N,W;

	while(cin>>N>>W){

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

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

		

		//01背包 

		memset(f,0,sizeof f);

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

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

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

		}	

		

		cout<<f[W]<<endl;

	}

}

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

using namespace std;

 

#define int long long int

#define ld long double

#define ll long long

#define pb push_back

#define F first

#define S second

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

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

 

typedef vector<ll> vi;

typedef pair<ll,ll> pii;

typedef vector<pii> vpii;

typedef vector<vi> vvi;

typedef map<ll,ll> mii;

typedef map<char,ll> mci;

 

ll gcd(ll a, ll b){

	if(b==0)return a;

	else return gcd(b, a%b);

}



signed main(){

    ll test=1;

    // cin>>test;

    while(test--){

        ll n, w; cin>>n>>w;

       long long  wt[10000], val[10000];

        rep(i, 0, n)cin>>wt[i]>>val[i];

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

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

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

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

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

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

        	}

        }

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

 

    }    

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

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



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

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

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

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[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: 2.317200380199144x):
#include <bits/stdc++.h>

using namespace std;

const int   N=1e4+10;

long long w[N],v[N];

int main()

{

	long long n,m;

	cin>>n>>m;

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

	{

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

	}

long long f[n+1][m+1];

memset(f,0,sizeof f);

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

	{

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

		{

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

			if(j>=w[i])

			{

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

			}

		}

	}

	cout<<f[n][m]<<endl;

   return 0;

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

#define ll long long

using namespace std;

#define inf 0x3f3f3f3f 

int main(){

	ll  n , W; cin >> n >> W;

    ll w[101] , v[101] , dp[100001] = {0};

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

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

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

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

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



    cout<< dp[W] <<endl;

}

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

using namespace std;

const int   N=1e4+10;

long long w[N],v[N];

int main()

{

	long long n,m;

	cin>>n>>m;

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

	{

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

	}

long long f[n+1][m+1];

memset(f,0,sizeof f);

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

	{

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

		{

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

			if(j>=w[i])

			{

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

			}

		}

	}

	cout<<f[n][m]<<endl;

   return 0;

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

using namespace std;

typedef long long ll;





ll w[105],f[100005];

ll v[105];



signed main()

{

	ll N,W;

	while(cin>>N>>W){

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

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

		

		//01背包 

		memset(f,0,sizeof f);

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

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

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

		}	

		

		cout<<f[W]<<endl;

	}

}

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

using namespace std;

const int   N=1e4+10;

long long w[N],v[N];

int main()

{

	long long n,m;

	cin>>n>>m;

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

	{

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

	}

long long f[n+1][m+1];

memset(f,0,sizeof f);

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

	{

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

		{

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

			if(j>=w[i])

			{

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

			}

		}

	}

	cout<<f[n][m]<<endl;

   return 0;

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

using namespace std;



#define pb		push_back

#define eb		emplace_back

#define mk		make_pair

#define fi		first

#define se		second

#define cc(x)	cout << #x << " = " << x << endl

#define ok		cout << "ok" << endl

#define endl	'\n'



typedef long long ll;

typedef pair<int,int> ii;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1.0);

 

const ll N = 1e5 + 10;

ll dp[N], p[N], v[N];

ll n, w;



int main() {

    	ios_base::sync_with_stdio(false);



	memset(dp, -INF, sizeof dp);    

	cin >>n >>w;



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

		cin >>p[i] >>v[i];

	}



	dp[0] = 0;

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

		for(int j = N-1; j-p[i] >= 0; j--){

			dp[j] = max(dp[j], dp[j-p[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: 2.267672637179288x):
#include <bits/stdc++.h>

#define PI acos(-1)

#define falcon ios_base::sync_with_stdio(false) ; cin.tie(NULL) ;

typedef long long ll ;

using namespace std ;



int main()

{

    falcon ;



    vector <ll> weights , costs ;



    ll n , w ;

    cin >> n >> w ;

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

    weights.push_back(0) ;

    costs.push_back(0) ;

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

    {

        ll weight , cost ;

        cin >> weight >> cost ;

        weights.push_back(weight) ;

        costs.push_back(cost) ;

    }

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

    {

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

        {

            if(i == 0 || j == 0) dp[i][j] = 0 ;

            else

            {

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

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

            }

        }

    }

    cout << dp[w][n] ;

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

#define ll long long

using namespace std;

#define inf 0x3f3f3f3f 

int main(){

	ll  n , W; cin >> n >> W;

    ll w[101] , v[101] , dp[100001] = {0};

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

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

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

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

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



    cout<< dp[W] <<endl;

}

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

#define PI acos(-1)

#define falcon ios_base::sync_with_stdio(false) ; cin.tie(NULL) ;

typedef long long ll ;

using namespace std ;



int main()

{

    falcon ;



    vector <ll> weights , costs ;



    ll n , w ;

    cin >> n >> w ;

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

    weights.push_back(0) ;

    costs.push_back(0) ;

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

    {

        ll weight , cost ;

        cin >> weight >> cost ;

        weights.push_back(weight) ;

        costs.push_back(cost) ;

    }

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

    {

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

        {

            if(i == 0 || j == 0) dp[i][j] = 0 ;

            else

            {

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

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

            }

        }

    }

    cout << dp[w][n] ;

}