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



using namespace std;



mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



#define hash sodnf9843bsd

#define ll long long

#define INF (1<<29)

#define INFF 0x7fffffff

#define LINF (1ll<<60)

#define LINFF 0x7fffffffffffffff

#define PI 3.14159265359

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

#define _fj(n) for(int j = 0;j < n;j++)

#define _fk(n) for(int k = 0;k < n;k++)

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

#define rall(x) x.rbegin(), x.rend()

#define YESNO(ans) cout << (ans?"YES":"NO") << endl

#define prec(x) cout << fixed << setprecision(x)

#define pqueue priority_queue

#define pb push_back

#define eb emplace_back

#define mp make_pair

#define mt make_tuple

#define endl '\n'



const ll maxn = 100;

const ll maxv = 100000;

ll iw[maxn+7];

ll dp[maxn+7][maxv+7] = {};

int iv[maxn+7];

int n, w;



ll solve(int i, int j){

    if (j == 0) return 0;

    if (j < 0 || i == n) return LINF;



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

        dp[i][j] = min(solve(i+1, j-iv[i])+iw[i], solve(i+1, j));

    }

    return dp[i][j];

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);



    cin>>n>>w;

    _fi(n) cin>>iw[i]>>iv[i];



    int ans = 0;

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

        if (solve(0, i) <= w) ans = i;

    }

    cout << ans << endl;





    return 0;

}


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



using namespace std;



mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



#define hash sodnf9843bsd

#define ll long long

#define INF (1<<29)

#define INFF 0x7fffffff

#define LINF (1ll<<60)

#define LINFF 0x7fffffffffffffff

#define PI 3.14159265359

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

#define _fj(n) for(int j = 0;j < n;j++)

#define _fk(n) for(int k = 0;k < n;k++)

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

#define rall(x) x.rbegin(), x.rend()

#define YESNO(ans) cout << (ans?"YES":"NO") << endl

#define prec(x) cout << fixed << setprecision(x)

#define pqueue priority_queue

#define pb push_back

#define eb emplace_back

#define mp make_pair

#define mt make_tuple

#define endl '\n'



const ll maxn = 100;

const ll maxv = 100000;



int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);



    ll iw[maxn+7];

    int iv[maxn+7];

    int n, w;cin>>n>>w;

    _fi(n) cin>>iw[i]>>iv[i];



    ll dp[maxv+7] = {};

    for(int i = 1;i <= maxv;i++) dp[i] = LINF;

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

        for(int j = maxv;j >= iv[i];j--){

            dp[j] = min(dp[j], iw[i]+dp[j-iv[i]]);

        }

    }



    ll ans = 0;

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

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

    }

    cout << ans << endl;



    return 0;

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

#define ll long long

#define ld long double

#define foru(i,a,n) for(ll i=(a); i<=(n); ++i)

#define ford(i,n,a) for(ll i=(n); i>=(a); --i)

using namespace std;

const int M = 101010;

const ll inf = 1e17;

ll n, m, w[111], v[111], dp[111][M];



int main(){

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

	cin >>n >>m;

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



	dp[0][0] = 0;

	foru(i,1,M-1) dp[0][i] = inf;

	foru(i,1,n) foru(j,1,M-1){

		if(j < v[i])

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

		else

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

	}

	

	ll ans = 0;

	foru(j, 1, M-1) if(dp[n][j] <= m) ans = j;

	cout <<ans;

	return 0;

}


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

#define ll long long

#define ld long double

#define foru(i,a,n) for(ll i=(a); i<=(n); ++i)

#define ford(i,n,a) for(ll i=(n); i>=(a); --i)

using namespace std;

const int M = 101010;

const ll inf = 1e17;

ll n, m, w[111], v[111], dp[M];



int main(){

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

	cin >>n >>m;

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



	dp[0] = 0;

	foru(i,1,M-1) dp[i] = inf;	//ko co cai nay la sai day nhe



	foru(i,1,n) ford(j,M-1,v[i])

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

	

	ll ans = 0;

	foru(j, 1, M-1) if(dp[j] <= m) ans = j;

	cout <<ans;

	return 0;

}
// Slower C++ solution:


#include <bits/stdc++.h>

#include <stdio.h>

#include <algorithm>

 

using namespace std;

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

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

#include <bits/stdc++.h>

#include <stdio.h>

#include <algorithm>

 

using namespace std;

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

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

#define l(s) s.length()

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

#define scan(v,n) rep(i,0,n) {ll k; cin >> k; v.pb(k);}

#define print(v,n) {rep(i,0,n) cout << v[i] << " "; cout << endl;}

#define printstr(s,n) {rep(i,0,n) cout << s[i]; cout << endl;}

#define rev(a) reverse(a.begin(), a.end());

#define pb push_back

typedef long long ll;

typedef long double lld;

typedef vector<pair<ll,ll>> vpi;

typedef vector<ll> vi;

 

const ll mxN=1e5+1;

const ll N=1e18+7;

 

ll dp[mxN+1];

 

  int main() {

      int T=1;// cin >> T;

      while(T--){

          ll n,W,sum=0; cin >> n >> W;

          rep(i,1,100001) dp[i]=N;

          rep(i,0,n) {

              ll w,v;

              cin >> w >> v;

              sum+=v;

              rrep(x,100001,0) {

                  if(x>=v&&dp[x]>dp[x-v]+w) dp[x]=dp[x-v]+w;

              }

          }

          ll ans=0;

          rrep(i,mxN-1,0){

              if(dp[i]<=W){

                  cout << i;

                  break;

              }

          }

          //cout << ans;

      } 

	 return 0;

}


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


#include <bits/stdc++.h>

#include <stdio.h>

#include <algorithm>

 

using namespace std;

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

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

#include <bits/stdc++.h>

#include <stdio.h>

#include <algorithm>

 

using namespace std;

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

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

#define l(s) s.length()

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

#define scan(v,n) rep(i,0,n) {ll k; cin >> k; v.pb(k);}

#define print(v,n) {rep(i,0,n) cout << v[i] << " "; cout << endl;}

#define printstr(s,n) {rep(i,0,n) cout << s[i]; cout << endl;}

#define rev(a) reverse(a.begin(), a.end());

#define pb push_back

typedef long long ll;

typedef long double lld;

typedef vector<pair<ll,ll>> vpi;

typedef vector<ll> vi;

 

const ll mxN=1e5;

const ll N=1e9+7;

 

int dp[mxN+1];



//dp[i][j][2] is the score of each player when the remaining array is from index i to j

// dp[0][n-1]=0

//rep(i,1,n+1) cout max of dp[i][i-1][1]







  int main() {

      int T=1;// cin >> T;

      while(T--){

          ll n,W,sum=0; cin >> n >> W;

          rep(i,1,mxN+1) dp[i]=N;

          rep(i,0,n) {

              ll w,v;

              cin >> w >> v;

              sum+=v;

              rrep(x,sum,0) {

                  if(x>=v&&dp[x]>dp[x-v]+w) dp[x]=dp[x-v]+w;

              }

          }

          ll ans=0;

          rrep(i,sum,0){

              if(dp[i]<=W) {

                  cout << i; 

                  break;

              }

          }

          //cout << ans;

          

      } 

	 return 0;

}
// Slower C++ solution:
#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';

}


// Faster C++ solution for the same problem (measured speedup: 1.3011479673399788x):
#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';

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.3464088698957215x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 1.8744059536592603x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 2.5126267088574448x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.3815244409696938x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 2.392362333641626x):
#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;

   			}

}
// Slower C++ solution:
#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;

     }

 }

}


// Faster C++ solution for the same problem (measured speedup: 2.9243794238170997x):
#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;

   			}

}