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

#include<stdlib.h>

#define VMAX 20000



int main() {



	unsigned short *A, *B;



	int C[VMAX + 1], n, i;

	scanf("%d", &n);



	A = (unsigned short*)malloc(sizeof(short) * n + 1);

	B = (unsigned short*)malloc(sizeof(short) * n + 1);



	for (i = 0; i <= VMAX; i++) C[i] = 0;



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

		scanf("%hu", &A[i+1]);

		C[A[i+1]]++;

	}



	for (i = 1; i <= VMAX; i++) C[i] += C[i-1];



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

		B[C[A[i]]] = A[i];

		C[A[i]]--;

	}



	printf("%d", B[1]);

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

		printf(" %d", B[i]);

	}

	printf("\n");



	free(A);

	free(B);

	return 0;

}




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

#include<stdlib.h>

#define MAX(x, y) (((x) > (y)) ? (x) : (y))



int main() {



	unsigned short *A, *B;



	int n, i, max;

	scanf("%d", &n);



	A = (unsigned short*)malloc(sizeof(short) * n + 1);

	B = (unsigned short*)malloc(sizeof(short) * n + 1);



	max = (1<<30)*-1;

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

		scanf("%hu", &A[i+1]);

		max = MAX(max, A[i+1]);

	}



	int C[max+1] = {0};



	for (i = 0; i < n; i++) C[A[i+1]]++;

	for (i = 1; i <= max; i++) C[i] += C[i-1];



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

		B[C[A[i]]] = A[i];

		C[A[i]]--;

	}



	printf("%d", B[1]);

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

		printf(" %d", B[i]);

	}

	printf("\n");



	free(A);

	free(B);

	return 0;

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

#include<stdlib.h>

#define MAX 20000001

#define VMAX 20000



int main() {



	unsigned short *A, *B;



	int C[VMAX + 1];

	int n, i, j;

	scanf("%d", &n);



	A = (unsigned short*)malloc(sizeof(short) * n + 1);

	B = (unsigned short*)malloc(sizeof(short) * n + 1);



	for (i = 0; i <= VMAX; i++) C[i] = 0;



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

		scanf("%hu", &A[i+1]);

		C[A[i+1]]++;

	}



	for (i = 1; i <= VMAX; i++) C[i] = C[i] + C[i-1];



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

		B[C[A[j]]] = A[j];

		C[A[j]]--;

	}



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

		if (i > 1) printf(" ");

		printf("%d", B[i]);

	}

	printf("\n");



	return 0;

}




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

#include<stdlib.h>

#include<string.h>

#define MAX(x, y) (((x) > (y)) ? (x) : (y))



int main() {



	int n, i, max;

	scanf("%d", &n);



	unsigned short A[n+1];

	unsigned short B[n+1];



	max = (1<<30)*-1;

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

		scanf("%hu", &A[i+1]);

		max = MAX(max, A[i+1]);

	}

	int C[max+1];

	memset(C, 0, sizeof(C));



	for (i = 0; i < n; i++) C[A[i+1]]++;

	for (i = 1; i <= max; i++) C[i] += C[i-1];



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

		B[C[A[i]]] = A[i];

		C[A[i]]--;

	}



	printf("%d", B[1]);

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

		printf(" %d", B[i]);

	}

	printf("\n");



	return 0;

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

#include<stdlib.h>

#define VMAX 20000



int main() {



	unsigned short *A, *B;



	int C[VMAX + 1], n, i;

	scanf("%d", &n);



	A = (unsigned short*)malloc(sizeof(short) * n + 1);

	B = (unsigned short*)malloc(sizeof(short) * n + 1);



	for (i = 0; i <= VMAX; i++) C[i] = 0;



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

		scanf("%hu", &A[i+1]);

		C[A[i+1]]++;

	}



	for (i = 1; i <= VMAX; i++) C[i] += C[i-1];



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

		B[C[A[i]]] = A[i];

		C[A[i]]--;

	}



	printf("%d", B[1]);

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

		printf(" %d", B[i]);

	}

	printf("\n");



	free(A);

	free(B);



	return 0;

}


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

#include<stdlib.h>

#include<string.h>

#define MAX(x, y) (((x) > (y)) ? (x) : (y))



int main() {



	int n, i, max;

	scanf("%d", &n);



	unsigned short A[n+1];

	unsigned short B[n+1];



	max = (1<<30)*-1;

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

		scanf("%hu", &A[i+1]);

		max = MAX(max, A[i+1]);

	}

	int C[max+1];

	memset(C, 0, sizeof(C));



	for (i = 0; i < n; i++) C[A[i+1]]++;

	for (i = 1; i <= max; i++) C[i] += C[i-1];



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

		B[C[A[i]]] = A[i];

		C[A[i]]--;

	}



	printf("%d", B[1]);

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

		printf(" %d", B[i]);

	}

	printf("\n");



	return 0;

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

#include<stdlib.h>

#define VMAX 20000



int main() {



	unsigned short *A, *B;



	int C[VMAX + 1], n, i;

	scanf("%d", &n);



	A = (unsigned short*)malloc(sizeof(short) * n + 1);

	B = (unsigned short*)malloc(sizeof(short) * n + 1);



	for (i = 0; i <= VMAX; i++) C[i] = 0;



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

		scanf("%hu", &A[i+1]);

		C[A[i+1]]++;

	}



	for (i = 1; i <= VMAX; i++) C[i] += C[i-1];



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

		B[C[A[i]]] = A[i];

		C[A[i]]--;

	}



	printf("%d", B[1]);

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

		printf(" %d", B[i]);

	}

	printf("\n");



	free(A);

	free(B);

	return 0;

}




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

#include<stdlib.h>

#include<string.h>

#define MAX(x, y) (((x) > (y)) ? (x) : (y))



int main() {



	int n, i, max;

	scanf("%d", &n);



	unsigned short A[n+1];

	unsigned short B[n+1];



	max = (1<<30)*-1;

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

		scanf("%hu", &A[i+1]);

		max = MAX(max, A[i+1]);

	}

	int C[max+1];

	memset(C, 0, sizeof(C));



	for (i = 0; i < n; i++) C[A[i+1]]++;

	for (i = 1; i <= max; i++) C[i] += C[i-1];



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

		B[C[A[i]]] = A[i];

		C[A[i]]--;

	}



	printf("%d", B[1]);

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

		printf(" %d", B[i]);

	}

	printf("\n");



	return 0;

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

using namespace std;int n,i,j,k[9999999];main(){scanf("%d",&n);for (i=0; i<n;i++){scanf("%d",&k[i]);}sort(k,k+n);for (i=0;i<n;i++){if(i){printf(" ");}printf("%d",k[i]);}printf("\n");}

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

#include<algorithm>

using namespace std;

int x[2000003],p[10003],n;

int main(){

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

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

		while(true){

			char c = getchar_unlocked();

			if('0' <= c && c <= '9'){

				x[i] = x[i] * 10 + (c - '0');

			}

			else{break;}

		}

		p[x[i]]++;

	}

	int c=0;

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

		for(int j=0;j<p[i];j++){

			if(c)printf(" ");c++;

			printf("%d",i);

		}

	}

	printf("\n");

	return 0;

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

#include <array>

#include <vector>



using namespace std;



int main()

{

        vector< int > vec;

        int n, tmp;



        cin >> n;

        array< int, 10001 > arr;



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

        {

                arr[i] = 0;

        }



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

        {

                cin >> tmp;

                arr[tmp]++;

        }



        /* Counting Sort */

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

        {

                if ( arr[i] != 0 )

                {

                        tmp = i;

                        for ( int j = 0 ; j < arr[tmp] ; j++ )

                        {

                                vec.push_back( tmp );

                        }

                }

        }





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

        {

                if ( i != n - 1 )

                {

                        cout << vec[i] << " ";

                }

                else

                {

                        cout << vec[i] << endl;

                }



        }





        return 0;

}

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



using namespace std;



#define MAX 2000005

#define INF 10001



int ary_a[MAX];

int ary_b[MAX];



void CountingSort( int ary_size ) {

	int ary_c[INF] = {0};

	int i = 0, j = 0;



	for ( j = 1 ; j <= ary_size ; j++ ) {

		//数値の出現回数を記録する

		ary_c[ary_a[j]]++;

	}



	for ( i = 1 ; i < INF ; i++ ) {

		// i以下の数値の出現回数を記録していく[

		ary_c[i] = ary_c[i] + ary_c[i-1];

	}



	for ( j = 1 ; j <= ary_size ; j++ ) {

		ary_b[ary_c[ary_a[j]]] = ary_a[j];

		ary_c[ary_a[j]]--;

	}

}



int main() {

	int number = 0;

	scanf( "%d", &number );



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

		scanf( " %d", &ary_a[i+1] );

	}



	CountingSort( number );



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

		if ( i > 1 ) { fprintf( stdout, " " ); }

		fprintf( stdout, "%d", ary_b[i] );

	}

	fprintf( stdout, "\n" );

	return 0;

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

using namespace std;



#define VMAX 10001



int main()

{

    int i, n, val, max, C[VMAX];

    cin >> n;

    max = 0;



    for(val = 0; val < VMAX; val++) C[val] = 0;



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

        cin >> val;

        C[val] = C[val] + 1;

        if(max < val) max = val;

    }

    for(val = 0; C[val] == 0; val++);

    cout << val;

    C[val] = C[val] - 1;



    while(val <= max){

        if(C[val] > 0){

            cout << " " << val;

            C[val] = C[val] - 1;

        }else{

            val++;

        }

    };

    cout << endl;    



    return 0;

}

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



#define VMAX 10001



int main()

{

    int i, n, val, max, C[VMAX];

    scanf("%d", &n);

    max = 0;



    for(val = 0; val < VMAX; val++) C[val] = 0;



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

        scanf("%d", &val);

        C[val] = C[val] + 1;

        if(max < val) max = val;

    }

    for(val = 0; C[val] == 0; val++);

    printf("%d", val);

    C[val] = C[val] - 1;



    while(val <= max){

        if(C[val] > 0){

            printf(" %d", val);

            C[val] = C[val] - 1;

        }else{

            val++;

        }

    };

    printf("\n");



    return 0;

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

#include <iostream>

#include <vector>



#include <string.h>



using namespace std;



typedef long long ll;



template<class T>

inline bool chmax(T &a, T b) {

    if(a < b) {

        a = b;

        return true;

    }

    return false;

}



template<class T>

inline bool chmin(T &a, T b) {

    if(a > b) {

        a = b;

        return true;

    }

    return false;

}



const int MAX_N = 100;

const int MAX_V = 10000;



int dp[MAX_N + 1][MAX_V + 1];



int solve(int n, int j, const int N, const int W, const vector<int> v, const vector<int> w) {

    if (dp[n][j] >= 0) {

        return dp[n][j];

    }



    if (j >= w[n]) {

        chmax(dp[n][j], solve(n - 1, j - w[n], N, W, v, w) + v[n]);

    }

    chmax(dp[n][j], solve(n - 1, j, N, W, v, w));



    return dp[n][j];

}



int main(void) {

    int N, W;

    cin >> N >> W;

    vector<int> v(N + 1);

    vector<int> w(N + 1);

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

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

    }



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

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

        dp[i][0] = 0;

    }

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

        dp[0][i] = 0;

    }



    solve(N, W, N, W, v, w);



    cout << dp[N][W] << endl;

    

    return 0;

}




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

#include <cassert>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <vector>



#include <limits.h>



using namespace std;



typedef long long ll;



template<class T>

inline bool chmax(T &a, T b) {

    if(a < b) {

        a = b;

        return true;

    }

    return false;

}



template<class T>

inline bool chmin(T &a, T b) {

    if(a > b) {

        a = b;

        return true;

    }

    return false;

}



// {value, weight}

vector<pair<int, int>> items;



int main(void) {

    int N, W;

    cin >> N >> W;



    items.resize(N + 1);

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

        int v, w;

        cin >> v >> w;

        items[i + 1] = {v, w};

    }



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



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

        auto item = items[i + 1];

        vector<int> tmp_dp = dp;

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

            if (j - item.second >= 0) {

                chmax(tmp_dp[j], dp[j - item.second] + item.first);

            }

        }

        dp = move(tmp_dp);

    }



    cout << dp[W] << endl;



    return 0;

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

#include <cstring>



using namespace std;



int memo[100][10001];

int value[100];

int weight[100];

int NEGA_INF = -10000000;



int dp(int k, int w) {

    if (w < 0) { return NEGA_INF; }

    if (k == -1 || w < 0) { return 0; }

    if (memo[k][w] != -1) { return memo[k][w]; }

    return memo[k][w] = max(

            dp(k - 1, w - weight[k]) + value[k],

            dp(k - 1, w));

}



int main() {

    int n, w;

    cin >> n >> w;

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

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

    }

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

    cout << dp(n - 1, w) << endl;

}

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



using namespace std;



int dp[101][10001];

int value[100];

int weight[100];

int NEGA_INF = -10000000;



int main() {

    int n, w;

    cin >> n >> w;

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

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

    }



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

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

            dp[i][j] = max(

                    dp[i - 1][j],

                    j - weight[i - 1] >= 0 ? dp[i - 1][j - weight[i - 1]] + value[i - 1] : 0);

        }

    }

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

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

typedef long long ll;

typedef unsigned long long ull;

using namespace std;

#define pb push_back

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

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



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

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

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

#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

#define mp make_pair

#define fi first

#define sc second

ll n;

ll v[200],w[200];

ll W;



ll done[200][20000];

ll memo[200][20000];



ll solve(ll i,ll j) {

	if(done[i][j]) {

		return memo[i][j];

	}

	if(i >= n) {

		return 0;

	}



	if(j + w[i] > W) {

		return solve(i + 1,j);

	}



	ll ret = max(solve(i + 1,j),solve(i + 1,j + w[i]) + v[i]);

	done[i][j] = true;

	return memo[i][j] = ret;

}



int main(){

	cin >> n >> W;

	REP(i,n) {

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

	}

	cout << solve(0,0) << endl;

	return 0;

}




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

#include<algorithm>

using namespace std;



int dp[10001];

int N,W;

int main() {

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



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

        int v,w;

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

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

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

        }

    }

    printf("%d\n",dp[W]);

    return 0;

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

#define ll long long

using namespace std;





int N, v[100], w[100], W;

int V[101][10001] {0};

int main(){

  cin >> N >> W;

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

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

  }

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

    for(int k = 1; k <= 10000; k++){

      if(k >= w[i]){

	V[i+1][k] = max(v[i] + V[i][max(0,k - w[i])], V[i][k]);

      }else{

	V[i+1][k] = V[i][k];

      }

      

    }

  }



  cout << V[N][W] << endl;

  

}

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

#include <iostream>

#include <algorithm>

#define ll long long

#define INF 100000000000000

using namespace std;



int main(){

  ll N, W;

  cin >> N >> W;

  ll v[100], w[100];

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

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

  }

  ll dp[N+1][W+1];

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

    for(ll k = 0; k < W + 1; k++){

      dp[i][k] = 0;

    }

  }



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

    for(ll k = 1; k <= W; k++){

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

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

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

      }

    }

  }

  cout << dp[N][W] << endl;

  



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



#define INF 1 << 30



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

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

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



using namespace std;



int main()

{

  int n, W; cin >> n >> W;

  vector<int> v(n);

  vector<int> w(n);

  REP(i,n) cin >> v[i] >> w[i];

  // vector<int> dp(10001,0);

  // REP(i,n) DOWN(j, W, w[i])

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

  // cout << *max_element(dp.begin(),dp.begin()+W+1) << endl;

  vector<int> dp(100001,INF);

  dp[0] = 0;

  REP(i,n) DOWN(j,100000,v[i])

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

  DOWN(i,100000,0) if(dp[i] <= W)

  {

    cout << i << endl;

    break;

  }

}

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



#define INF 1 << 30



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

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

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



using namespace std;



int main()

{

  int n, W; cin >> n >> W;

  vector<int> v(n);

  vector<int> w(n);

  REP(i,n) cin >> v[i] >> w[i];

  vector<int> dp(10001,0);

  REP(i,n) DOWN(j, W, w[i])

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

  cout << *max_element(dp.begin(),dp.begin()+W+1) << endl;

}
// Slower C++ solution:


#include <cstdio>

#include <algorithm>

using namespace std;



int dp(int, int);



int w[1001];

int v[101];

int memo[101][10001];



int main(){

    int N,W;

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

    

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

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

            memo[i][j] = -1;

        }

    }



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

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

    }



    printf("%d\n",dp(N,W));



    return 0;

}





int dp(int i,int j){

    if(i == 0){

        return 0;

    }

    if(memo[i][j] >= 0){

        return memo[i][j];

    }

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

        return memo [i][j] = dp(i - 1,j);

    }



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

}




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


#include <cstdio>

#include <algorithm>

using namespace std;



int dp(int, int);



int N,W;

int w[1001];

int v[101];



int main(){

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



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

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

    }



    int dp[101][10001];

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

        dp[0][i] = 0;

    }



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

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

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

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

            }else{

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

            }

        }

    }



    printf("%d\n",dp[N][W]);



    return 0;

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

#include <algorithm>

using namespace std;



int memo[101][10001],v[1001],w[1001];

int dp(int i,int j){

    if(i == 0)return 0;

    if(memo[i][j] >= 0)return memo[i][j];

    if(j - w[i - 1] < 0)return memo[i][j] = dp(i - 1,j);



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

}



int main(){

    int N,W;

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

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

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

    }

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

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

            memo[i][j] = -1;

        }

    }

    printf("%d\n",dp(N,W));

    return 0;

}


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

#include <algorithm>

using namespace std;



int v[1001],w[1001];

int N,W,i,j;

int dp[101][10001];

int main(){

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

    for(j = 0; j < W; j++)dp[0][j] = 0;

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

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

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

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

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

        }

    }

    printf("%d\n",dp[N][W]);

    return 0;

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

#include <algorithm>

#include <string.h>

using namespace std;



const int MAX_N=100;

const int MAX_W=10000;

int w[MAX_N];

int v[MAX_N];

int dp[MAX_N+1][MAX_W+1];

int n,W;



int rec(int i,int j){

	if(dp[i][j]>=0){

		return dp[i][j];

	}

	int res;

	if(i==n){

		res=0;

	}

	else if(j<w[i]){

		res=rec(i+1,j);

	}

	else{

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

	}

	return dp[i][j]=res;

}

int main(){

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

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

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

	}

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

	printf("%d\n",rec(0,W));

	return 0;



}

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

#include <algorithm>

using namespace std;

const int MAX_N=100;

const int MAX_W=10000;

int n,W;

int v[MAX_N];

int w[MAX_N];

int dp[MAX_N+1][MAX_W+1];

void solve(){ 

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

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

              if(j<w[i]){

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

                        }

                else{

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

                   }

           }

   }



      }

int main(){

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

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

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

         dp[i][0]=0;

         }

solve();

printf("%d\n",dp[n][W]);

return 0;

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

#include <cstdio>

#include <algorithm>

#include <string.h>



#define MAX_N   100

#define MAX_W   10000



using namespace std;



int n, W;

int w[MAX_N], v[MAX_N];



int dp[MAX_N + 1][MAX_W + 1];



int rec(int i, int j)

{

  if (dp[i][j] >= 0) {

    // すでに調べたことがあるならばその結果を再利用

    return dp[i][j];

  }

  int res;

  if (i == n) {

    res = 0;

  } else if (j < w[i]) {

    res = rec(i + 1, j);

  } else {

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

  }

  // 結果をテーブルに記憶する

  return dp[i][j] = res;

}



void solve()

{

  // まだ調べられていないことを表す-1でメモ化テーブルを初期化

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

  printf("%d\n", rec(0, W));

}



int main(void)

{

  int i;

  cin >> n >> W;



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

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

  }



  solve();



  return 0;

}

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

#include <cstdio>

#include <algorithm>

#include <string.h>



#define MAX_N   100

#define MAX_W   10000



using namespace std;



int n, W;

int w[MAX_N], v[MAX_N];



int dp[MAX_N + 1][MAX_W + 1];   // DPテーブル



void solve()

{

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

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

      if (j < w[i]) {

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

      } else {

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

      }

    }

  }

  printf("%d\n", dp[n][W]);

}



int main(void)

{

  int i;

  cin >> n >> W;



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

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

  }



  solve();



  return 0;

}