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

#include <array>

#include <cassert>

#include <iostream>

#include <vector>

using namespace std;



template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }

template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }



void dbg_out() { cerr << endl; }

template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }



#ifdef NEAL_DEBUG

#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#else

#define dbg(...)

#endif





const int INF = 1e9 + 5;

const int V_TOTAL_MAX = 1e5 + 5;



int main() {

    ios::sync_with_stdio(false);

#ifndef NEAL_DEBUG

    cin.tie(nullptr);

#endif



    int N, W;

    cin >> N >> W;

    vector<int> dp(V_TOTAL_MAX, INF);

    dp[0] = 0;



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

        int w, v;

        cin >> w >> v;



        for (int tot = V_TOTAL_MAX - 1; tot >= 0; tot--)

            if (dp[tot] < INF)

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

    }



    int ans = V_TOTAL_MAX - 1;



    while (dp[ans] > W)

        ans--;



    cout << ans << '\n';

}


// Optimized solution to the same problem (faster):
#include <algorithm>

#include <array>

#include <cassert>

#include <iostream>

#include <vector>

using namespace std;



template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }

template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }



void dbg_out() { cerr << endl; }

template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }



#ifdef NEAL_DEBUG

#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#else

#define dbg(...)

#endif





const int INF = 1e9 + 5;

const int N_MAX = 100;

const int V_MAX = 1000;



int main() {

    ios::sync_with_stdio(false);

#ifndef NEAL_DEBUG

    cin.tie(nullptr);

#endif



    int N, W;

    cin >> N >> W;

    vector<int> dp(N_MAX * V_MAX + 1, INF);

    dp[0] = 0;



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

        int w, v;

        cin >> w >> v;



        for (int tot = i * V_MAX; tot >= 0; tot--)

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

    }



    int ans = N_MAX * V_MAX;



    while (dp[ans] > W)

        ans--;



    cout << ans << '\n';

}


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

#include<memory.h>

#include<algorithm>

#include<vector>

using namespace std;

#define INF 0x7ffffffff

int main()

{

    int N, W;

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

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

    vector<int>w(N);

    vector<int>v(N);

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

    {

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

    }

    vector<vector<long> > dp(N+1, vector<long>(N*1000+1, INF));

    dp[0][0] = 0;

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

    {

        for(int j=0; j<=N*1000; j++)

        {

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

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

        }

    }

    long ans = 0;

    for(long i=0; i<=N*1000; i++)

    {

       if(dp[N][i] <= W)ans = max(ans, i);

    }

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

    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

#include<memory.h>

#include<algorithm>

#include<vector>

using namespace std;

#define INF 0x7ffffffff

int main()

{

    int N, W;

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

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

    vector<int>w(N);

    vector<int>v(N);

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

    {

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

    }

    vector<long> dp(N*1000+1, INF);

    dp[0] = 0;

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

    {

        for(int j=N*1000; j>=v[i]; j--)

        {

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

        }

    }

    long ans = 0;

    for(long i=0; i<=N*1000; i++)

    {

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

    }

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

    return 0;

}

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

#include <cstdio>

#include <vector>

#include <queue>

#include <algorithm>

#include <iomanip>

#include <stack>

#include <cstring>

#include <string>



using namespace std;

#define long long long



const int N = 1e5 + 10;

const long INF = 1e9 + 7;



int n, total;

long w[N], v[N], f[110][N];



int main()

{

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

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

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



    cin >> n >> total;

    for (int i = 1; i <= n; ++i) cin >> w[i] >> v[i];



    fill(f[0], f[0] + N, INF); f[0][0] = 0;

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

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

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

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

        }

    int res = 0;

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

        if (f[n][j] <= total) res = j;

    cout << res;



    return 0;

}


// Optimized solution to the same problem (faster):
#define taskname ""



#include <iostream>

#include <algorithm>



using namespace std;

#define long long long



const int N = 1e5 + 10;

const long INF = 1e16;



int n, total;

typedef pair<int, int> pii;

pii pack[N];

long f[N];



int main()

{

//    freopen(taskname".INP", "r", stdin);

//    freopen(taskname".OUT", "w", stdout);

    cin.tie(nullptr); ios_base::sync_with_stdio(false);



    cin >> n >> total;

    for (int i = 1; i <= n; ++i) cin >> pack[i].first >> pack[i].second;



    fill(f, f + N, INF); f[0] = 0;



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

        for (int val = N - 1; val; --val)

            if (val >= pack[i].second) f[val] = min(f[val], f[val - pack[i].second] + pack[i].first);



    for (int val = N - 1; val; --val)

        if (f[val] <= total) {cout << val; return 0;}



    return 0;

}


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



using namespace std;



typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vl;



typedef ll _loop_int;

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

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

#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)



#define DEBUG(x) cout<<#x<<": "<<x<<endl

#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl

#define ALL(a) (a).begin(),(a).end()



const ll MOD = 1000000007ll;

#define FIX(a) ((a)%MOD+MOD)%MOD



template<class T> inline bool chmin(T& a, T b) {

    if (a > b) { a = b; return true; }

    return false;

}

template<class T> inline bool chmax(T& a, T b) {

    if (a < b) { a = b; return true; }

    return false;

}



int n;

ll w;



const int MAXN = 100;

const ll MAXV = 1000*MAXN+5;

ll dp[MAXV];



int main() {

    cin>>n>>w;



    fill(dp,dp+MAXV,1e9 + 5);

    dp[0] = 0;



    REP(i,n){

        ll a,b;

        cin>>a>>b;

        FORR(j,0,MAXV-b){

            if(dp[j] != -1)

                chmin(dp[j+b], dp[j]+a);

        }

    }



    ll ans = 0;



    REP(i,MAXV){

        if(dp[i] <= w)

            chmax(ans,i);

    }

    cout << ans << endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vl;

typedef pair<int,int> pii;



typedef int _loop_int;

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

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

#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)



#define DEBUG(x) cout<<#x<<": "<<x<<endl

#define DEBUG2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl

#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl

#define DEBUG_ARR(v,n) cout<<#v<<":";REP(i,n)cout<<" "<<v[i];cout<<endl

#define ALL(a) (a).begin(),(a).end()



const ll MOD = 1000000007ll;

#define FIX(a) ((a)%MOD+MOD)%MOD



template<class T> inline bool chmin(T& a, T b) {

    if (a > b) { a = b; return true; }

    return false;

}

template<class T> inline bool chmax(T& a, T b) {

    if (a < b) { a = b; return true; }

    return false;

}



int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    int N,W;

    cin>>N>>W;

    vi w(N), v(N);

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



    int V = N*1000;

    vl dp(V+5, numeric_limits<ll>::max());

    dp[0] = 0;

    REP(i,N){

        FORR(j,0,V){

            if(dp[j] != numeric_limits<ll>::max())

                chmin(dp[j + v[i]], dp[j] + w[i]);

        }

    }

    //DEBUG_VEC(dp);



    ll ans = 0;

    REP(i,V+1){

        if(dp[i] <= W)

            chmax(ans,(ll)i);

    }

    cout << ans << endl;

    return 0;

}

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

using namespace std;

#define mod 1000000007

using ll = long long;



int main() {

    // 入力

    int N, W;

    cin >> N >> W;

    vector<ll>w(N);

    vector<ll>v(N);

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

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

    }



    ll INF = 10000000000000;

    // i+1番目以降で価値j以上の時の重さの最小値がdp[i][j]

    // 価値の総和の最大値はN*10^3

    vector<vector<ll>> dp(N+1, vector<ll>(N*1000 + 1, INF));



    for (int i = N-1; i >= 0; --i) {

        dp[i][0] = 0;

        for (int j = 1; j <= N*1000; ++j){

            if(j <= v[i]){

                // DP[][j-v[i]]が0になるので

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

            }else{

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

            }

        }

    }



    // 二部探索、容量Wで価値vが可能ならば(dp[0][v] <= W) == true、vの最大値lbを求める

    // lb == 0の時は価値0なのでそのままでいい

    int lb=0, ub = N*1000 + 1;

    while( ub-lb > 1 ){

        int mid = (lb + ub) / 2;

        if (dp[0][mid] <= W) {

            lb = mid;

        } else {

            ub = mid;

        }

    }



    cout << lb;

    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

using ll = long long;



// N個(価値v, 重さw), 重さの総和W以下, O(n \sigma v_i)

ll knapsack2(int N, int W, vector<ll> v, vector<ll> w){

    ll INF = 10000000000000;

    ll V_MAX = 0; // 価値の総和の最大値V_MAX

    for (int x : v) {

        V_MAX += x;

    }



    // i+1番目以降で価値j以上の時の重さの最小値がdp[i][j]

    vector<vector<ll>> dp(N+1, vector<ll>(V_MAX + 1, INF));

    for (int i = N-1; i >= 0; --i) {

        dp[i][0] = 0;

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

            if(j <= v[i]){

                // DP[][j-v[i]]が0になるので

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

            }else{

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

            }

        }

    }



    // 価値で線形探索(二分探索もできるが必要ない)

    int res = 0;

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

        if(dp[0][i] <= W) res = i;

    }

    return res;

}



int main() {

    // 入力

    int N, W;

    cin >> N >> W;

    vector<ll>w(N);

    vector<ll>v(N);

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

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

    }



    ll ans = knapsack2(N, W, v, w);

    cout << ans;

    return 0;

}

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

#define ll long long int

#define ull unsigned long long 

#define ff first

#define ss second

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

#define pb push_back 

#define mp make_pair

#define inf 1000000000000000

#define mod 1000000007

using namespace std;



int main()

{ 



fast;

	ll n,w;

	cin>>n>>w;



	ll wt[n],val[n];

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

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



	ll dp[n+1][100009];

	

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

	for(ll j=0;j<100009;j++)

	dp[i][j]=inf;



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

			dp[i][0]=0;

		

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

	{

		for(ll j=1;j<100001;j++)

		{

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

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

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

		}

	}

 ll ans=0;

    

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

    {

        for(ll j=i;j<100001;j++)

        {

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

            ans=max(ans,j);

        }

    }

    cout<<ans<<endl;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define ll long long int

#define ull unsigned long long 

#define ff first

#define ss second

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

#define pb push_back 

#define mp make_pair

#define inf 3000000000000000

#define mod 1000000007

using namespace std;



int main()

{ 

  fast;

   ll n,w;

   cin>>n>>w;



   ll wt[n],val[n];

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

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



   vector<ll> dp(100009,inf);

   dp[0]=0;



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

   	for(ll j=100008;j>-1;j--)

   		if(j>=val[i])

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



   		for(ll i=100008;i>-1;i--)

   			if(dp[i]<=w)

   			{

   				cout<<i<<endl;

   				return 0;

   			}

}

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

#define ll long long int

#define ull unsigned long long 

#define ff first

#define ss second

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

#define pb push_back 

#define mp make_pair

#define inf 1000000000000000

#define mod 1000000007

using namespace std;



int main()

{ 



fast;

	ll n,w;

	cin>>n>>w;



	ll wt[n],val[n];

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

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



	ll dp[n+1][100001];

	

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

	for(ll j=0;j<100001;j++)

	dp[i][j]=inf;



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

			dp[i][0]=0;

		

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

	{

		for(ll j=1;j<100001;j++)

		{

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

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

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

		}

	}

 for(ll i=100000;i>-1;i--)

 {

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

     {

         cout<<i<<endl;

         return 0;

     }

 }

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define ll long long int

#define ull unsigned long long 

#define ff first

#define ss second

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

#define pb push_back 

#define mp make_pair

#define inf 3000000000000000

#define mod 1000000007

using namespace std;



int main()

{ 

  fast;

   ll n,w;

   cin>>n>>w;



   ll wt[n],val[n];

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

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



   vector<ll> dp(100009,inf);

   dp[0]=0;



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

   	for(ll j=100008;j>-1;j--)

   		if(j>=val[i])

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



   		for(ll i=100008;i>-1;i--)

   			if(dp[i]<=w)

   			{

   				cout<<i<<endl;

   				return 0;

   			}

}

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

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int, int> pi;

#define debug(x) cout << #x << ": " << x << endl

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

#define rep(i, a) for(int i = 0; i < (int)(a); i++)

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

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define endl '\n'



ll dp[100005];



int main(){

	ios_base::sync_with_stdio(false);

	cin.tie(0);

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

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

	int n;

	ll w;

	cin >> n >> w;

	rep(i, 100005) dp[i] = 1e18;

	dp[0] = 0;

	rep(i, n){

		ll a;

		int b;

		cin >> a >> b;

		for(int j = 100000 - b; j >= 0; j--){

			dp[j + b] = min(dp[j + b], dp[j] + a);

		}

	}

	int ans;

	rep(i, 100001) if(dp[i] <= w) ans = i;

	cout << ans << endl;

	return 0;

}

/*

Things to look out for:

	- Integer overflows

	- Array bounds

	- Special cases

Be careful!

*/


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int, int> pi;

#define debug(x) cout << #x << ": " << x << endl

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

#define rep(i, a) for(int i = 0; i < (int)(a); i++)

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

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define endl '\n'



ll dp[100005];



int main(){

	ios_base::sync_with_stdio(false);

	cin.tie(0);

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

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

	int n;

	ll w;

	cin >> n >> w;

	rep(i, 100005) dp[i] = 1e18;

	dp[0] = 0;

	repn(i, 1, n + 1){

		ll a;

		int b;

		cin >> a >> b;

		for(int j = 1000 * i - b; j >= 0; j--){

			dp[j + b] = min(dp[j + b], dp[j] + a);

		}

	}

	int ans = 0;

	rep(i, 100001) if(dp[i] <= w) ans = i;

	cout << ans << endl;

	return 0;

}

/*

Things to look out for:

	- Integer overflows

	- Array bounds

	- Special cases

Be careful!

*/


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

using namespace std;

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

#define scn(n) scanf("%d",&n)

#define lscn(n) scanf("%lld",&n)

typedef long long ll;

#define pri(n) printf("%d\n",n)

#define lpri(n) printf("%lld\n",n);

#define rep(i,st,ed) for(int i=st;i<ed;i++)

#define F first

#define S second 

#define pb(n) push_back(n)

const int N=1e5+6;

const ll M=1e9+7;



int main()

{

	int n,w;

	scn(n);scn(w);

	ll dp[n+1][N];

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

	{

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

			dp[i][j]=M;

	}



	// think of it as minimum weight for a particular value

	// the value can be at max 1e5. this if the key of the 

	// problem

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

	{

		int wt,val;

		scn(wt);scn(val);

		if(dp[i-1][val]==M)

			dp[i][val]=wt;

		else dp[i][val]=min(dp[i][val],1ll*wt);

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

		{

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

			if(j>=val)

			{

				if(dp[i-1][j-val]!=M)

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

			}

		}

	}

	ll ans=0;

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

	{

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

		{			

			// lpri(dp[n][i]);

			ans=i;

			break;

		}

	}

	lpri(ans);

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

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

#define scn(n) scanf("%d",&n)

#define lscn(n) scanf("%lld",&n)

typedef long long ll;

#define pri(n) printf("%d\n",n)

#define lpri(n) printf("%lld\n",n);

#define rep(i,st,ed) for(int i=st;i<ed;i++)

#define var(n) int n; scn(n)

#define F first

#define S second 

#define pb push_back

const int N=1e5+5;

// const ll M = 998244353;

const ll M=1e9+7;

const ll inf=1e18;



int dp[N]; 



int main()

{

	var(n);var(w);

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

		dp[i] = M;

	rep(i,0,n)

	{

		var(wt);

		var(val);

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

		{			

			if(dp[j]!=M)

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

		}

		dp[val] = min(dp[val],wt);

		

	}

	int ans = 0;

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

	{

		int wt = dp[i];

		if(wt<=w)

		{

			ans = i;

			break;

		}

	}

	pri(ans);

}

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

using namespace std;



#define lli long long int

#define pb push_back





main()

{

    lli n,c,a,b,i,j;

    cin>>n>>c;

    lli w[n],v[n];

    lli dp[100001];



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

    {

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

    }

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

    {

        dp[i] = c+1;

    }

    dp[0] = 0;

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

    {

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

        {

            if(dp[j-v[i]] < c)

            {

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

            }

        }

    }



    for(i=100000;i>=0;i--)

    {

        if(dp[i]<=c)

        {

            cout<<i;

            break;

        }

    }

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;



#define lli long long int

#define pb push_back

#define f first

#define sec second



bool compare(const pair<lli,lli> &i, const pair<lli,lli> &j )

{

    return i.sec <= j.sec;

}



main()

{

    lli n,i,j,a,b,c,t,cap,w,val,sum=0;

    vector<pair<lli,lli>> v;



    cin>>n>>cap;



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

    {

        cin>>a>>b;

        v.pb({b,a});

        sum += b;

    }



    lli dp[sum+1];

    dp[0] = 0;



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

    {

        dp[i] = cap+1;

    }



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

    {

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

        {

            if(dp[j-v[i].f] < cap)

            {

                dp[j] = min(dp[j-v[i].f]+v[i].sec, dp[j]);

            }

        }

    }



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

    {

        if(dp[i]<=cap)

        {

            cout<<i;

            return 0;

        }

    }

}


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

#include<bits/stdc++.h>

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

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

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

#define endl '\n'

#define ll long long int

#define ff first

#define ss second

#define pb push_back

#define mod 1000000007

#define M 998244353

#define inf 1e9+10

using namespace std;



ll dp[105][100005];



int main()

{

    fast; 

    ll n,mx,i,j,m=100005,ans=0,x;

    cin>>n>>mx;

    ll w[n+1],v[n+1];

    f(i,1,n+1)

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

    

    f(i,0,n+1)

    	dp[i][0]=0;

    f(j,1,m)

    	dp[0][j]=inf;



    f(i,1,n+1)

    {

    	f(j,1,m)

    	{

    		if(j>=v[i])

    		{

    			x=w[i]+dp[i-1][j-v[i]];

    			if(dp[i-1][j]>x)

    			{

    				dp[i][j]=x;

    				if(x<=mx)

    					ans=max(ans,j);

    			}

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

    		}

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

    	}

    }

    cout<<ans;

}


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

#include<bits/stdc++.h>

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

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

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

#define endl '\n'

#define ll long long int

#define ff first

#define ss second

#define pb push_back

#define mod 1000000007

#define M 998244353

#define inf 1e9+10

using namespace std;



ll dp[100005];



int main()

{

    fast; 

    ll n,mx,i,j,m=100005,ans=0,x;

    cin>>n>>mx;

    ll w[n+1],v[n+1];

    f(i,1,n+1)

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

    

    dp[0]=0;

    f(j,1,m)

    	dp[j]=inf;



    f(i,1,n+1)

    {

    	fr(j,m-1,1)

    	{

    		if(j>=v[i])

    		{

    			x=w[i]+dp[j-v[i]];

    			if(dp[j]>x)

    			{

    				dp[j]=x;

    				if(x<=mx)

    					ans=max(ans,j);

    			}

    		}

    	}

    }

    cout<<ans;

}


// Fastest known solution for this problem: