stablegradients/pie-gem5-pairs huggingface dataset:
// 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.763496521999637x):
#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>

using namespace std;



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

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

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

#define pb push_back

#define mk make_pair

#define ff first

#define ss second

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



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;

typedef vector<ll> vll;



const int M=1e5+5;

const ll INF=1e15;

const int MOD=1e9+5;



int n,W;

ll dp[M][105],valor[105],peso[105];



ll ks(int w,int x){

  if (w < 0) return -INF;

  if (x > n) return 0;

  if (dp[w][x] != -1) return dp[w][x];

  dp[w][x] = max(ks(w,x+1) , valor[x] + ks(w-peso[x],x+1));

  return dp[w][x];

}



void ini(){

  fp(i,0,M)

    fp(j,1,n+1) dp[i][j] = -1;

}



int main(){



	fastio;

  cin >> n >> W;

  ini();

  fp(i,1,n+1) cin >> peso[i] >> valor[i];

  cout << ks(W,1) << "\n";



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 8.92032880825186x):
#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>

using namespace std;



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

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

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

#define pb push_back

#define mk make_pair

#define ff first

#define ss second

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



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;

typedef vector<ll> vll;



const int M=1e5+5;

const ll INF=1e15;

const int MOD=1e9+5;



int n,W;

ll dp[M][105],valor[105],peso[105];



ll ks(int w,int x){

  if (w < 0) return -INF;

  if (x > n) return 0;

  if (dp[w][x] != -1) return dp[w][x];

  dp[w][x] = max(ks(w,x+1) , valor[x] + ks(w-peso[x],x+1));

  return dp[w][x];

}



void ini(){

  fp(i,0,M)

    fp(j,1,n+1) dp[i][j] = -1;

}



int main(){



	fastio;

  cin >> n >> W;

  ini();

  fp(i,1,n+1) cin >> peso[i] >> valor[i];

  cout << ks(W,1) << "\n";



	return 0;

}


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

//#pragma GCC optimize("Ofast")

//#pragma GCC target("avx,avx2,fma")



using namespace std;



typedef long long ll;



//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>pb_ds;



#define IN freopen("in.txt","r",stdin)

#define OUT freopen("out.txt","w",stdout)

#define pi pair<int,int>

#define F first

#define S second

#define pb push_back

#define pp pop_back

#define mod 1000000007

#define pai acos(-1)

#define N 100005



ll Weight[N],Profit[N],dp[2][N];



int main ()

{

   ios_base::sync_with_stdio(false);

   cin.tie(NULL);

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

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

      cin>>Weight[i]>>Profit[i];

   }

   fill(dp[0],dp[0]+2*N,-INT_MAX*105);

   dp[(n+1)%2][0]=0;

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

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

         ll op1=dp[(i+1)%2][s];

         ll op2=(s-Weight[i]>=0)?Profit[i]+dp[(i+1)%2][s-Weight[i]]:0ll;

         dp[i%2][s]=max(op1,op2);

      }

   }

   ll ans=0;

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

   cout<<ans<<"\n";

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



#define ll long long

#define ull unsigned long long

#define ld long double



#define tiii tuple < int, int, int >

#define pii pair < int, int >

#define pll pair < ll, ll >

#define pci pair < char, int >

#define psi pair < string, int >

#define pis pair < int, string >



#define vi vector < int >

#define vd vector < double >

#define vld vector < ld >

#define vll vector < ll >

#define vs vector < string >

#define vc vector < char >

#define vpi vector < pii >

#define vpll vector < pll >

#define vpis vector < pis >



#define pb push_back

#define mt make_tuple

#define gt0 get < 0 >

#define gt1 get < 1 >

#define gt2 get < 2 >



#define pi acos(-1)



#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)



using namespace std;



const int maxn = 1e5 + 5;

const int mod = 1e9 + 9;



ll n, w;

ll weight[105], value[105];

ll dp[105][maxn];



ll fnc(ll pos, ll baki)

{

    if(pos > n) return 0;



    if(dp[pos][baki]) return dp[pos][baki];



    ll p = 0, q = 0;



    if(baki >= weight[pos]) p = fnc(pos + 1, baki - weight[pos]) + value[pos];



    q = fnc(pos + 1, baki);



    return dp[pos][baki] = max(p, q);

}



int main()

{

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

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



    fast;



    cin >> n >> w;



    for(ll i = 1; i <= n; i++) cin >> weight[i] >> value[i];



    cout << fnc(1LL, w) << 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.7894945467073775x):
#include "bits/stdc++.h"



#define ll long long

#define ull unsigned long long

#define ld long double



#define tiii tuple < int, int, int >

#define pii pair < int, int >

#define pll pair < ll, ll >

#define pci pair < char, int >

#define psi pair < string, int >

#define pis pair < int, string >



#define vi vector < int >

#define vd vector < double >

#define vld vector < ld >

#define vll vector < ll >

#define vs vector < string >

#define vc vector < char >

#define vpi vector < pii >

#define vpll vector < pll >

#define vpis vector < pis >



#define pb push_back

#define mt make_tuple

#define gt0 get < 0 >

#define gt1 get < 1 >

#define gt2 get < 2 >



#define pi acos(-1)



#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)



using namespace std;



const int maxn = 1e5 + 5;

const int mod = 1e9 + 9;



ll n, w;

ll weight[105], value[105];

ll dp[105][maxn];



ll fnc(ll pos, ll baki)

{

    if(pos > n) return 0;



    if(dp[pos][baki]) return dp[pos][baki];



    ll p = 0, q = 0;



    if(baki >= weight[pos]) p = fnc(pos + 1, baki - weight[pos]) + value[pos];



    q = fnc(pos + 1, baki);



    return dp[pos][baki] = max(p, q);

}



int main()

{

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

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



    fast;



    cin >> n >> w;



    for(ll i = 1; i <= n; i++) cin >> weight[i] >> value[i];



    cout << fnc(1LL, w) << 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.779638374386696x):
#include "bits/stdc++.h"



#define ll long long

#define ull unsigned long long

#define ld long double



#define tiii tuple < int, int, int >

#define pii pair < int, int >

#define pll pair < ll, ll >

#define pci pair < char, int >

#define psi pair < string, int >

#define pis pair < int, string >



#define vi vector < int >

#define vd vector < double >

#define vld vector < ld >

#define vll vector < ll >

#define vs vector < string >

#define vc vector < char >

#define vpi vector < pii >

#define vpll vector < pll >

#define vpis vector < pis >



#define pb push_back

#define mt make_tuple

#define gt0 get < 0 >

#define gt1 get < 1 >

#define gt2 get < 2 >



#define pi acos(-1)



#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)



using namespace std;



const int maxn = 1e5 + 5;

const int mod = 1e9 + 9;



ll n, w;

ll weight[105], value[105];

ll dp[105][maxn];



ll fnc(ll pos, ll baki)

{

    if(pos > n) return 0;



    if(dp[pos][baki]) return dp[pos][baki];



    ll p = 0, q = 0;



    if(baki >= weight[pos]) p = fnc(pos + 1, baki - weight[pos]) + value[pos];



    q = fnc(pos + 1, baki);



    return dp[pos][baki] = max(p, q);

}



int main()

{

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

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



    fast;



    cin >> n >> w;



    for(ll i = 1; i <= n; i++) cin >> weight[i] >> value[i];



    cout << fnc(1LL, w) << endl;



    return 0;

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

using namespace std;



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

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

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

#define pb push_back

#define mk make_pair

#define ff first

#define ss second

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



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;

typedef vector<ll> vll;



const int M=1e5+5;

const ll INF=1e15;

const int MOD=1e9+5;



int n,W;

ll dp[M][105],valor[105],peso[105];



ll ks(int w,int x){

  if (w < 0) return -INF;

  if (x > n) return 0;

  if (dp[w][x] != -1) return dp[w][x];

  dp[w][x] = max(ks(w,x+1) , valor[x] + ks(w-peso[x],x+1));

  return dp[w][x];

}



void ini(){

  fp(i,0,M)

    fp(j,1,n+1) dp[i][j] = -1;

}



int main(){



	fastio;

  cin >> n >> W;

  ini();

  fp(i,1,n+1) cin >> peso[i] >> valor[i];

  cout << ks(W,1) << "\n";



	return 0;

}


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



#define ll long long

#define ull unsigned long long

#define ld long double



#define tiii tuple < int, int, int >

#define pii pair < int, int >

#define pll pair < ll, ll >

#define pci pair < char, int >

#define psi pair < string, int >

#define pis pair < int, string >



#define vi vector < int >

#define vd vector < double >

#define vld vector < ld >

#define vll vector < ll >

#define vs vector < string >

#define vc vector < char >

#define vpi vector < pii >

#define vpll vector < pll >

#define vpis vector < pis >



#define pb push_back

#define mt make_tuple

#define gt0 get < 0 >

#define gt1 get < 1 >

#define gt2 get < 2 >



#define pi acos(-1)



#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)



using namespace std;



const int maxn = 1e5 + 5;

const int mod = 1e9 + 9;



ll n, w;

ll weight[105], value[105];

ll dp[105][maxn];



ll fnc(ll pos, ll baki)

{

    if(pos > n) return 0;



    if(dp[pos][baki]) return dp[pos][baki];



    ll p = 0, q = 0;



    if(baki >= weight[pos]) p = fnc(pos + 1, baki - weight[pos]) + value[pos];



    q = fnc(pos + 1, baki);



    return dp[pos][baki] = max(p, q);

}



int main()

{

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

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



    fast;



    cin >> n >> w;



    for(ll i = 1; i <= n; i++) cin >> weight[i] >> value[i];



    cout << fnc(1LL, w) << endl;



    return 0;

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

//#pragma GCC optimize("Ofast")

//#pragma GCC target("avx,avx2,fma")



using namespace std;



typedef long long ll;



//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>pb_ds;



#define IN freopen("in.txt","r",stdin)

#define OUT freopen("out.txt","w",stdout)

#define pi pair<int,int>

#define F first

#define S second

#define pb push_back

#define pp pop_back

#define mod 1000000007

#define pai acos(-1)

#define N 100005



ll Weight[N],Profit[N],dp[2][N];



int main ()

{

   ios_base::sync_with_stdio(false);

   cin.tie(NULL);

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

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

      cin>>Weight[i]>>Profit[i];

   }

   fill(dp[0],dp[0]+2*N,-INT_MAX*105);

   dp[(n+1)%2][0]=0;

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

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

         ll op1=dp[(i+1)%2][s];

         ll op2=(s-Weight[i]>=0)?Profit[i]+dp[(i+1)%2][s-Weight[i]]:0ll;

         dp[i%2][s]=max(op1,op2);

      }

   }

   ll ans=0;

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

   cout<<ans<<"\n";

   return 0;

}




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



#define ll long long

#define ull unsigned long long

#define ld long double



#define tiii tuple < int, int, int >

#define pii pair < int, int >

#define pll pair < ll, ll >

#define pci pair < char, int >

#define psi pair < string, int >

#define pis pair < int, string >



#define vi vector < int >

#define vd vector < double >

#define vld vector < ld >

#define vll vector < ll >

#define vs vector < string >

#define vc vector < char >

#define vpi vector < pii >

#define vpll vector < pll >

#define vpis vector < pis >



#define pb push_back

#define mt make_tuple

#define gt0 get < 0 >

#define gt1 get < 1 >

#define gt2 get < 2 >



#define pi acos(-1)



#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)



using namespace std;



const int maxn = 1e5 + 5;

const int mod = 1e9 + 9;



ll n, w;

ll weight[105], value[105];

ll dp[105][maxn];



ll fnc(ll pos, ll baki)

{

    if(pos > n) return 0;



    if(dp[pos][baki]) return dp[pos][baki];



    ll p = 0, q = 0;



    if(baki >= weight[pos]) p = fnc(pos + 1, baki - weight[pos]) + value[pos];



    q = fnc(pos + 1, baki);



    return dp[pos][baki] = max(p, q);

}



int main()

{

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

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



    fast;



    cin >> n >> w;



    for(ll i = 1; i <= n; i++) cin >> weight[i] >> value[i];



    cout << fnc(1LL, w) << 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.267461288166909x):
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;



ll dp[100005][105];



int main(){

    ios::sync_with_stdio(false);

    cin.tie(NULL); cout.tie(NULL);





    int n, W;

    cin>>n>>W;



    vector<int> weights(n), values(n);



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

        cin>>weights[i];

        cin>>values[i];

    }





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

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

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



            if(w >= weights[i])

                dp[w][i] = max(dp[w][i], dp[w-weights[i]][i-1] + values[i]);

        }

    }



    cout<<dp[W][n-1];





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

using namespace std;

typedef long long int ll;



ll dp[100005][105];



int main(){

    ios::sync_with_stdio(false);

    cin.tie(NULL); cout.tie(NULL);





    int n, W;

    cin>>n>>W;



    vector<int> weights(n), values(n);



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

        cin>>weights[i];

        cin>>values[i];

    }





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

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

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



            if(w >= weights[i])

                dp[w][i] = max(dp[w][i], dp[w-weights[i]][i-1] + values[i]);

        }

    }



    cout<<dp[W][n-1];





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

using namespace std;

typedef long long int ll;



ll dp[100005][105];



int main(){

    ios::sync_with_stdio(false);

    cin.tie(NULL); cout.tie(NULL);





    int n, W;

    cin>>n>>W;



    vector<int> weights(n), values(n);



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

        cin>>weights[i];

        cin>>values[i];

    }





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

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

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



            if(w >= weights[i])

                dp[w][i] = max(dp[w][i], dp[w-weights[i]][i-1] + values[i]);

        }

    }



    cout<<dp[W][n-1];





    return 0;

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

using namespace std;



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

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

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

#define pb push_back

#define mk make_pair

#define ff first

#define ss second

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



typedef long long ll;

typedef pair<int,int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;

typedef vector<ll> vll;



const int M=1e5+5;

const ll INF=1e15;

const int MOD=1e9+5;



int n,W;

ll dp[M][105],valor[105],peso[105];



ll ks(int w,int x){

  if (w < 0) return -INF;

  if (x > n) return 0;

  if (dp[w][x] != -1) return dp[w][x];

  dp[w][x] = max(ks(w,x+1) , valor[x] + ks(w-peso[x],x+1));

  return dp[w][x];

}



void ini(){

  fp(i,0,M)

    fp(j,1,n+1) dp[i][j] = -1;

}



int main(){



	fastio;

  cin >> n >> W;

  ini();

  fp(i,1,n+1) cin >> peso[i] >> valor[i];

  cout << ks(W,1) << "\n";



	return 0;

}


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

using namespace std;

typedef long long int ll;



ll dp[100005][105];



int main(){

    ios::sync_with_stdio(false);

    cin.tie(NULL); cout.tie(NULL);





    int n, W;

    cin>>n>>W;



    vector<int> weights(n), values(n);



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

        cin>>weights[i];

        cin>>values[i];

    }





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

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

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



            if(w >= weights[i])

                dp[w][i] = max(dp[w][i], dp[w-weights[i]][i-1] + values[i]);

        }

    }



    cout<<dp[W][n-1];





    return 0;

}