stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main()

{

    int x;

    scanf("%d",&x);

    int arr[x+1];

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

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

    sort(arr,arr+x);

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

    {

        if(i==x-1)

            printf("%d\n",arr[i]);

        else

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

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#define MAX 2000001

#define VMAX 10001

#include <stdio.h>





int A[MAX], C[VMAX], B[MAX];



int main()//被排序的数至少有一个，所以B数组中的数统一向后移动一位 

{

	int n, i, j;

	scanf("%d", &n);

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

	{

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

	}

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

	{

		C[A[i]]++;

	}

	for(i=1;i<=VMAX;i++)

	{

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

	}

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

	{

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

		C[A[i]]--;

	}

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

	{

		if(i>1)

		{

			printf(" ");

		}

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

	}

	printf("\n");

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <string>

#include <set>

#include <cstdio>

#include <cstring>

#include <queue>

#include <stack>

#include <algorithm>

#include <cmath>

#define ll long long

#define INF 0x3f3f3f3f

#define SIS std::ios::sync_with_stdio(false)

using namespace std;



int main()

{

    SIS;

    int n;

    while(cin>>n)

    {

        vector <int> s;

        int num;

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

        {

            cin>>num;

            s.push_back(num);

        }

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

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

            if(i==0)

                cout<<s[i];

            else

                cout<<" "<<s[i];

        cout<<endl;

    }

    return 0;

}




// Optimized solution to the same problem (faster):
#define MAX 2000001

#define VMAX 10001

#include <stdio.h>





int A[MAX], C[VMAX], B[MAX];



int main()//被排序的数至少有一个，所以B数组中的数统一向后移动一位 

{

	int n, i, j;

	scanf("%d", &n);

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

	{

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

	}

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

	{

		C[A[i]]++;

	}

	for(i=1;i<=VMAX;i++)

	{

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

	}

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

	{

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

		C[A[i]]--;

	}

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

	{

		if(i>1)

		{

			printf(" ");

		}

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

	}

	printf("\n");

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int n,a[2000001],freq[100100];



void countingsort(int a[]){

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

        freq[a[i]]++;

    }

    int idx=0;

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

        for(int j=1;j<=freq[i];j++){

            idx++;

            a[idx]=i;

        }

    }

}



int main(){

    cin>>n;

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

        cin>>a[i];

    }

    countingsort(a);

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

        cout<<a[i];

        if(i==n){

            cout<<endl;

        }else{

            cout<<" ";

        }

    }

}


// Optimized solution to the same problem (faster):
#define MAX 2000001

#define VMAX 10001

#include <stdio.h>





int A[MAX], C[VMAX], B[MAX];



int main()//被排序的数至少有一个，所以B数组中的数统一向后移动一位 

{

	int n, i, j;

	scanf("%d", &n);

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

	{

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

	}

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

	{

		C[A[i]]++;

	}

	for(i=1;i<=VMAX;i++)

	{

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

	}

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

	{

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

		C[A[i]]--;

	}

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

	{

		if(i>1)

		{

			printf(" ");

		}

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

	}

	printf("\n");

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;



int A[2000005], B[2000005], C[10005];



void CountingSort(int n) {

    int k = 10000;

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



    for (int j = 0; j < n; j++) C[A[j]]++;



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



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

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

        C[A[j]]--;

    } 

}



int main() {

    int n;

    cin >> n;

    for (int i = 0; i < n; i++) cin >> A[i];

    CountingSort(n);

    for (int i = 0; i < n; i++) cout << B[i] << (i != n - 1 ? " " : "\n");

}


// Optimized solution to the same problem (faster):
/*

#include<iostream>

using namespace std;



int A[2000005], B[2000005], C[10005];



void CountingSort(int n) {

    int k = 10000;

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



    for (int j = 0; j < n; j++) C[A[j]]++;



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



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

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

        C[A[j]]--;

    } 

}



int main() {

    int n;

    cin >> n;

    for (int i = 0; i < n; i++) cin >> A[i];

    CountingSort(n);

    for (int i = 0; i < n; i++) cout << B[i] << (i != n - 1 ? " " : "\n");

}

*/



#include<stdio.h>

#include<stdlib.h>

#define MAX 2000001

#define VMAX 10000



int main() {

    unsigned short *A, *B;



    int C[VMAX + 1];

    int n, i, j;

    scanf("%d", &n);



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

    B = (unsigned short *)malloc(sizeof(unsigned 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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}




// Optimized solution to the same problem (faster):
#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;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}




// Optimized solution to the same problem (faster):
#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;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#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");}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}




// Optimized solution to the same problem (faster):
#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;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}




// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

  

}

// Optimized solution to the same problem (faster):
#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;

  



}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

  }

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):


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

}




// Optimized solution to the same problem (faster):


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

}


// Fastest known solution for this problem: