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

#define MAX 100005

#define pb push_back

#define mp make_pair

#define pii pair<long long,long long>

#define read(a) scanf("%d",&a)

#define p1(a) cout<<"Check "<<a<<endl;

#define p2(a,b) cout<<"Check "<<a<<' '<<b<<endl;

#define p3(a,b,c) cout<<"Check "<<a<<' '<<b<<' '<<c<<endl;

#define fo(i,n) for(i=0;i<n;i++)

#define ll long long

#define clr(a) memset(a,0,sizeof(a))

#define MOD 10000000000

#define INF 10000000000000;



using namespace std;



int n,cp;

ll cost[MAX];

int weight[MAX];

ll dp[105][MAX];



ll f(){

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

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

            if(weight[i-1]<=j){

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

            }

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

        }

    }

    return dp[n][cp];

}



int main()

{

    cin>>n>>cp;

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

        scanf("%d%lld",&weight[i],&cost[i]);

    }

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

        dp[0][i]=0;

    }

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

        dp[i][0]=0;

    }

    ll ans=f();



    cout<<ans<<endl;



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

#define INF 1073741824

#define ll long long

#define PI (2*acos(0.0))

#define Hare prllf("here\n")

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

#define mp make_pair

#define pb push_back

#define pii pair<ll,ll>

#define x first

#define y second

#define on(val,pos) val|(1<<pos)

#define off(val,pos) val&(~(1<<pos))

#define check(val,pos) (val&(1<<pos))



//first four adjacent,second four corner

//ll row[8]={0,-1,0,1,1,-1,-1,1};

//ll col[8]={-1,0,1,0,-1,-1,1,1};

using namespace std;



int main(){

    ll i,j,k,n,m,val,t=0,cnt,test;

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

    cin>>n>>k;

    ll arr[k+5];

    memset(arr,0,sizeof arr);

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

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

        for(j=k;j>=m;j--){

            arr[j]=max(arr[j],arr[j-m]+val);

        }

    }

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

    //free();   //if poller array

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



using namespace std;



int main(){

    int n,W;

    cin >> n >> W;

    int w[n+10],v[n+10];

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

        long ww,vv;

        cin >> ww >> vv;

        w[i] = ww;

        v[i] = vv;

    }



    long T[n+1][W+1] = {};

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

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

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

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

            }else{

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

            }

        }

    }



    cout << T[n][W] << endl;







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



using namespace std ;



int n ;

int m ;

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

int main(){

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

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

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

    }



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

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

        {

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

        }

    }

    printf("%lld",dp[m]);

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



#define long long long

using namespace std;



const int N = 1e5 + 5;

int n, W;

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



int main(){

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

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

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

    }

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

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

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

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

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

        }

    }

    printf("%lld\n", dp[n][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.3738986982825596x):
#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;

}
// 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.7659233724276522x):
/**

     **author : _KMS_

     **created : 29-03-2020

**/

#include<bits/stdc++.h>

using namespace std;

const long long M =1e5+10,MOD=998244353;

typedef long long ll;

ll dp[107][M];

vector<pair<ll,ll>>v;

int main() {

   

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n,w;

  cin>>n>>w;

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

 {

  ll a,b;

  cin>>a>>b;

  v.push_back({a,b});

 }

 sort(v.begin(),v.end());

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

  {



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

    {

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

      {

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

      }

      else

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

    }

  }

  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.2853373939688146x):
/**

     **author : _KMS_

     **created : 29-03-2020

**/

#include<bits/stdc++.h>

using namespace std;

const long long M =1e5+10,MOD=998244353;

typedef long long ll;

ll dp[107][M];

vector<pair<ll,ll>>v;

int main() {

   

  ios::sync_with_stdio(false);

  cin.tie(0);

  int n,w;

  cin>>n>>w;

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

 {

  ll a,b;

  cin>>a>>b;

  v.push_back({a,b});

 }

 sort(v.begin(),v.end());

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

  {



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

    {

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

      {

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

      }

      else

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

    }

  }

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

using namespace std;



const int MAXW = 1e5 + 10;



long long knapsack[MAXW];

int N,W;



int main(){



	cin >> N >> W;



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

		int w,v;

		cin >> w >> v;

		for(int i = W;i>=w;i--) knapsack[i] = max(knapsack[i-w] + v,knapsack[i]);

	}



	long long best = 0;

	for(int i = 0;i<=W;i++) best = max(best,knapsack[i]);

	cout << best << endl;



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

using namespace std;



const int MAXW = 1e5 + 10;



long long knapsack[MAXW];

int N,W;



int main(){



	cin >> N >> W;



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

		int w,v;

		cin >> w >> v;

		for(int i = W;i>=w;i--) knapsack[i] = max(knapsack[i-w] + v,knapsack[i]);

	}



	long long best = 0;

	for(int i = 0;i<=W;i++) best = max(best,knapsack[i]);

	cout << best << endl;



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

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n, w;

ll **mem;

pair<int, ll> *x;

ll nap(int i = 0, int rem = w)

{

    if(i == n)

        return 0;

    if(~mem[i][rem])

        return mem[i][rem];

    ll first = nap(i + 1, rem), second = 0;

    if(rem >= x[i].first)

        second = x[i].second + nap(i + 1, rem - x[i].first);

    return mem[i][rem] = max(first, second);

}

int main()

{

    //cin.tie(NULL); cout.tie(NULL);  ios_base::sync_with_stdio(false);

    #ifndef ONLINE_JUDGE

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

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

    #endif

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

    mem = new ll*[n];

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

    {

        mem[i] = new ll[w + 1];

        memset(mem[i], -1, (w + 1) * 8);

    }

    x = new pair<int, ll>[n];

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

        scanf("%d %lld", &x[i].first, &x[i].second);

    printf("%lld", nap());

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

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n, w;

ll **mem;

pair<int, ll> *x;

ll nap(int i = 0, int rem = w)

{

    if(i == n)

        return 0;

    if(~mem[i][rem])

        return mem[i][rem];

    ll first = nap(i + 1, rem), second = 0;

    if(rem >= x[i].first)

        second = x[i].second + nap(i + 1, rem - x[i].first);

    return mem[i][rem] = max(first, second);

}

int main()

{

    //cin.tie(NULL); cout.tie(NULL);  ios_base::sync_with_stdio(false);

    #ifndef ONLINE_JUDGE

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

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

    #endif

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

    mem = new ll*[n];

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

    {

        mem[i] = new ll[w + 1];

        memset(mem[i], -1, (w + 1) * 8);

    }

    x = new pair<int, ll>[n];

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

        scanf("%d %lld", &x[i].first, &x[i].second);

    printf("%lld", nap());

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

#include <algorithm>



// 0 for Weight index, 1 for Value index

long long arr[101][2];



// The first for Weight, the second for Value

// Notice that all the table is initialized to zero,

// because it's defined in global scope.

// Let's benefit from that.

long long table[100002][101];



int main()

{

	int n, w;

	std::cin >> n >> w;

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

		std::cin >> arr[i][0] >> arr[i][1];

	// It sets the initial row.

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

	{

		if (arr[0][0] <= i)

			table[i][0] = arr[0][1];

	}

	// The outer loop for the elements.

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

	{

		// the inner loop for the weight.

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

		{

			if (arr[j][0] > i)

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

			else

				table[i][j] = std::max(table[i][j - 1], static_cast<long long>(arr[j][1]) + table[i - arr[j][0]][j - 1]);

		}

	}

	std::cout << table[w][n - 1] << '\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.3065270438539334x):
#include <iostream>

#include <algorithm>



// 0 for Weight index, 1 for Value index

long long arr[101][2];



// The first for Weight, the second for Value

// Notice that all the table is initialized to zero,

// because it's defined in global scope.

// Let's benefit from that.

long long table[100002][101];



int main()

{

	int n, w;

	std::cin >> n >> w;

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

		std::cin >> arr[i][0] >> arr[i][1];

	// It sets the initial row.

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

	{

		if (arr[0][0] <= i)

			table[i][0] = arr[0][1];

	}

	// The outer loop for the elements.

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

	{

		// the inner loop for the weight.

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

		{

			if (arr[j][0] > i)

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

			else

				table[i][j] = std::max(table[i][j - 1], static_cast<long long>(arr[j][1]) + table[i - arr[j][0]][j - 1]);

		}

	}

	std::cout << table[w][n - 1] << '\n';

	return 0;

}