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

 

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

#define ll long long

#define ff first

#define ss second

 

const int maxn=105 ;

const int maxv=1005 ;

const int inf=1e9+10 ;

 

using namespace std ;

 

ll dp[maxn*maxv] ;

pair<ll,ll> v[maxn] ;

int ans ;

 

int main()

{

  lp(i,1,maxn*maxv) dp[i]=inf ;

  dp[0]=0;

 

  int n, w ;

 

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

  lp(i,0,n) scanf("%lld%lld", &v[i].ff, &v[i].ss) ;

 

  lp(i,0,n)

  {

    for(int j=ans+v[i].ss ; j >= v[i].ss ; j -- )

    {

      if(dp[ j-v[i].ss ] + v[i].ff <= w )

      {

        dp[j] = min(dp[j] , dp[ j-v[i].ss ] + v[i].ff ) , ans=max(ans,j) ;

      }

    }

  }

  printf("%d\n", ans) ;

}

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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

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

using namespace std;

const int inf = 2e9+7;



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

long long f[110][100100];



int main()

{

    int N, V, i, j;



    cin>>N>>V;



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

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

    fill(f[0],f[0]+100001,inf);

    f[0][0] = 0;

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

    {

        for(j=0;j<=100000;j++)

            if(j >= v[i])

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

            else

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

    }

    int res=0;

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

        if(f[N][i]<=V)

            res = i;



    cout<<res<<endl;



    return 0;

}

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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<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, 63, sizeof(f));

	f[0] = 0;

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

		int w, v;

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

		for (int i = maxn - 3; i >= v; i--)if (f[i - v] + w <= C) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= maxn - 3; i++)if (f[i] <= C)ans = max(ans, (LL)i);

	printf("%lld\n", ans);



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}


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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

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

#define ll long long

#define pb push_back

#define mod 1000000007

#define mp make_pair

#define pi acos(-1)

#define line cout<<"------------------"<<endl

#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);

#define filein freopen("input.txt","r",stdin)

#define fileout freopen("output.txt","w",stdout)

#define inf (int)1e9+7

using namespace std;

ll n ;

ll w[109],val[109];

ll dp[100009];

ll weight;

int  main()

{

    cin>>n>>weight;

    for(ll i=1;i<=100007;i++) dp[i]=inf;

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

    {

        cin>>w[i]>>val[i];

        for(ll j=100005;j>=val[i];j--)

        {

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

        }

    }

    for( ll i=100005;i>=0;i--)

    {

        if(dp[i]<=weight)

        {

            cout<<i<<endl;

            return 0;

        }

    }







}


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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

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

#include <vector>

#define ll long long int



using namespace std;



struct Item {

	ll weight;

	ll value;

};



const ll INF = 1LL << 32;

vector<ll> dp(100001, INF);



ll knapSack(ll W, Item items[], ll n){

	ll sum = dp[0] = 0;

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

		sum += items[i].value;

    	for(ll j = sum; j >= items[i].value; j--){

         	dp[j] = min(dp[j], dp[j - items[i].value] + items[i].weight);

    	}

	}

	

	for(ll i = sum; i >= 0; i--){

		if(dp[i] <= W){

			return i;

		}

	}

}



int main(){

	Item items[100];

	ll N, W;

	cin >> N >> W;

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

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

	cout << knapSack(W, items, N) << endl;

	return 0;

}

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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

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



using namespace std;

 

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

 

#define nl '\n'

 

#define y1 aza_ibagaliev

 

#define f first

#define s second

	

#define ed end()

#define bg begin()

#define rbg rbegin()

 

#define rv reverse

#define mp make_pair

#define pb push_back

#define ppb pop_back

#define ppf pop_front

 

#define sz size()

#define all(x) x.bg, x.ed

 

#define pll pair < ll, ll >

#define pii pair < int, int >

 

#define sqr(x) ((x) * 1ll * (x))

#define sqrd(x) ((x) * 1.0 * (x))

 

#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

 

#define rnl cout << "----------------------------------------" << nl

 

#define bit __builtin_popcount

 

inline ll bip(ll x, ll n, ll mod){ll res=1;while(n){if(n & 1){res=(res*x)%mod;}x=(x*x)%mod;n>>=1;}return res;}

        	

const int ppr = 257;

const ll INF = 2e18;

const int inf = 2e9;

const int mod = 1e9 + 7;

const int N = 1e5 + 123;

const ld pi = 3.1741592653589793238462643;

 

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

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



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

ll dp[N];



main() {             	

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

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



//	srand(time(NULL));



	cin >> n >> W;



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

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



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

		dp[i] = INF;

                       

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

		for(int j = 1e5; j >= 0; j--) 

			if(j - v[i] >= 0 && dp[j - v[i]] != INF) {

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

			}



	for(int i = 1e5; i >= 0; i--)

		if(dp[i] <= W) return cout << i, 0;



    return 0;                                        

}

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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

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



using namespace std;





typedef long long ll;



const int MAX = 1e5+5;

ll dp[MAX+MAX];



int n , W;







int main()

{



    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n>>W;



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

        dp[j] = LONG_LONG_MAX;





    dp[0] = 0;

    ll ans = 0;

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





        ll w , v;

        cin>>w>>v;



        for( int j = MAX ; j >= 0 ; j-- ) {



            if( dp[j] != LONG_LONG_MAX ) {



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

                if( dp[j+v] <= W )

                ans = max( ans , j+v );



            }



        }



    }



    cout<<ans<<"\n";

}


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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

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

#define ll long long

#define ull unsigned long long

#define IO ios::sync_with_stdio(false), cin.tie(0)

#define endl '\n'

#define main() int main()

#define ff1(i,n) for(int i=1;i<=n;++i)

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

#define pi acos(-1.0)

#define ms(a, x) memset(a, x, sizeof(a))

#define lowbit(x) ((x)&(-(x)))

#define pb push_back

#define binarycount __builtin_popcount(x)

#define tr t[root]

#define lson t[root << 1]

#define rson t[root << 1 | 1]

#define fir first

#define sec second

#define debug(x) cout<<x<<'\n'

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

#define sab(a, b) scanf("%d%d", &a, &b)

#define pa(a) printf("%d",a)

#define pab(a,b) printf("%d%d",a,b)

#define pii pair<string,int>

using namespace std;



#define maxn 1000010

const int inf = 0x3f3f3f3f;

const int mod = 9973;

const double eps = 1e-8;

ll gcd(ll a, ll b) {return b==0?a:gcd(b, a%b);}

ll lcm(ll a, ll b) {return a/gcd(a, b)*b;}

int max(int x,int y){if(x>y) return x;return y;}

ll powmod(ll a,ll b){

    ull ans = 1, pow = a%mod;

    while(b) { if(b&1) ans = (ans*pow)%mod; pow = (pow*pow)%mod; b >>= 1; }

    return ans%mod;

}

ll v[105],w[105];	

ll dp[maxn],n,W,ans;

main()

{

	IO;

	cin>>n>>W;

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

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

	}

	ans=0;

	ms(dp,0x3f);

	dp[0]=0;

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

		for(int j=1e5;j>=v[i];j--){

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

			if(dp[j]<=W) ans=max(ans,(ll)j);

		}

	}

	cout<<ans<<endl;

} 

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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

}
// Slower C++ solution:
// Author : Syed Mujtaba

// Seek knowledge from the Cradle to the Grave !!

// https://www.linkedin.com/in/syed-mujtaba-064a5016a 



#include <bits/stdc++.h>

using namespace std;

#define int     long long

#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

signed main()

{

	fast_io

	int n, w;

	cin >> n >> w;

	vector < int > wt(n), val(n);

	int dp[n + 1][100008] = {0};



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

		cin >> wt[i] >> val[i];

	for(int i = 0; i <= 100000; i++) // base case

	{

		if(i == 0)

			dp[1][0] = 0;

		else if(i == val[0] && wt[0] <= w)

			dp[1][i] = wt[0];

		else

			dp[1][i] = 1e18;

	}

	for(int i = 2; i <= n; i++) // tabulation

	{

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

		{

			dp[i][j] = 1e18;

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

			if(j - val[i - 1] >= 0)

				dp[i][j] = min(dp[i][j], dp[i - 1][j - val[i - 1]] + wt[i - 1]);

		}	

	}

	int ans;

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

	{

		if(dp[n][i] <= w)

			ans = i;

	}

	cout << ans << endl;

}

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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

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

#include<cstdio>

#include<algorithm>



using namespace std;



const int INF = 1e9 + 7;

const int MAX_V = 1e3 + 1;

const int MAX_N = 101;

int max_V;

int n,W;

int w[MAX_N],v[MAX_N];

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



//dp[i+1][j]:从前i件物品中得到价值为j时的最小重量,不存在就是INF

//转移的话,就看第i类是要还是不要

int solve(){

    fill(dp[0], dp[0] + MAX_V * MAX_N + 1, INF);//没有物品可拿,自然是INF

    dp[0][0] = 0;

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

        for (int j = 0; j <= max_V * n; j++){

            if(j<v[i]){

                dp[i + 1][j] = dp[i][j];//装不下

            }else{

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

            }

        }

    }

    int res = 0;

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

        

        if(dp[n][i]<=W){

            res = i;

            //cout << dp[n][i] << " ";

        }

        

    }

    return res;

}



int main(){

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

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

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

        max_V = max(max_V, v[i]);

    }

    cout << solve() << endl;

    return 0;

}

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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

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

using namespace std;

typedef long long ll;



//int from[1009];



int main()

{ 

  ll dp[100009];

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

    dp[i] = 10000000000000ll;

  ll w[109];

  int v[109];

  dp[0]= 0;

  int n;

  ll cap;

  ll sum = 0;

  cin >> n >> cap; 

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

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

    sum = sum + v[i]; 

  }

  //cout << sum << endl;

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



      int current = sum - v[i];

      for(int j = current; j>=0;j--){

        int index = j + v[i];

          //cout << j << " " << dp[index] << " " << dp[j]+w[i] << endl;

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

      

      }

      

      //cout << endl;

    

  }



  int ans = 0;

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

    if(dp[i]<=cap)

      ans = max(i,ans);

  }

  cout << ans << endl;



}

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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

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

#include<cstring>

#include<vector>

using namespace std;

const int maxn = 1e5 + 10;

long long w[maxn];

long long v[maxn];

long long dp[maxn];

int main(){

	int n,V;

	long long ans = 0;

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

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

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

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

    dp[0] = 0;

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

    {

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

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

    }

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

	if(dp[i]<=V) 

		ans = max(ans,(long long)i);

    printf("%lld\n",ans);

	return 0;

}


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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

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

#include<stdio.h>

#include<algorithm>

#include<cstring>

#include<queue>

#include<vector>

#define ll long long

#define pi acos(-1.0)

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 1e6+5;

int v[maxn];

ll dp[maxn], w[maxn];



int main(){

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

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

	int sum = 0;

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

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

		sum += v[i];

	}

	dp[0] = 0;

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

		for(int j = sum; j >= v[i]; j--)

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

	}

	for(int i = sum; i >= 0; i--){

		if(dp[i] <= W){

			cout << i << endl;

			break;

		}

	}

}

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

#define ll long long int

using namespace std;





int main()

{

    int n,W;

    cin>>n>>W;

    int val[n+5],wt[n+5];

    int sum=0;

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

        cin>>wt[i]>>val[i];

        sum+=val[i];

    }

    int dp[n+5][sum+5];

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

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

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

            else if(i==0) dp[i][j]=1e9;

            else if(val[i-1]<=j) dp[i][j]=min(wt[i-1]+dp[i-1][j-val[i-1]],dp[i-1][j]);

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



        }

    }

    int idx=0;

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

        if(dp[n][i]<=W)idx=i;

    }

    cout<<idx<<endl;











    return 0;

}