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

#include <map>

#include <unordered_map>

#include <bits/stdc++.h>



#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

#define mod 1000000007

#define ll long long

#define pb push_back

#define mp make_pair

#define gcd __gcd

#define F first

#define S second

#define PI 3.14159265358979323



using namespace std;







int main()

{

    ll n,w,wt[100010],value[100010],ans=0,mv=0;

    vector<ll>min_wt_for_val(100010,9999999999999);

    min_wt_for_val[0]=0;



    cin>>n>>w;

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

        cin>>wt[i]>>value[i];

        mv+=value[i];

    }



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

        for(ll val=100002;val>=value[item];val--){

            min_wt_for_val[val]=min(min_wt_for_val[val],min_wt_for_val[val-value[item]]+wt[item]);

        }

    }

    for(ll i=0;i<=mv;i++) if(min_wt_for_val[i]<=w) ans=max(ans,i);

    cout<<ans<<"\n";



return 0;

}

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

#include <map>

#include <unordered_map>

#include <bits/stdc++.h>



#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

#define mod 1000000007

#define ll long long

#define pb push_back

#define mp make_pair

#define gcd __gcd

#define F first

#define S second

#define PI 3.14159265358979323



using namespace std;







ll solve(vector<vector<ll> > &dp, vector< pair<ll,ll> > &v, ll n, ll mv)

{

    if(mv==0) return 0;

    if(n==0) return 9999999999999;

    if(dp[n][mv]!=-1) return dp[n][mv];



    ll one=9999999999999,two=9999999999999;

    if(mv>=v[n-1].S)  one=v[n-1].F+solve(dp, v, n-1, mv-v[n-1].S);

    two = solve(dp, v, n-1, mv);



    return dp[n][mv]=min(one,two);

}





int main()

{

    ll x,y,n,w,ans=0,mv=0,kk;

    cin>>n>>w;

    vector< pair<ll,ll> > v(n);

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

        cin>>x>>y;

        mv+=y;

        v[i]=mp(x,y);

    }

    vector<vector<ll> > dp( 110 , vector<ll> (mv+2,-1));



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

        kk=solve(dp,v,n,i);

        if(kk<=w) { ans=i;  break;  }

    }

    cout<<ans<<"\n";



return 0;

}

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

#define rep(i, m, n) for(int i = m; i < (n); i++)

#define rrep(i,m,n) for(int i = m; i >= n; i--)

#define print(x) cout << (x) << endl;

#define print2(x,y) cout << (x) << " " << (y) << endl;

#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;

#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}

#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;

#define INF (1e18)

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

typedef struct{

    ll to;

    ll cost;

} edge;

typedef pair<ll, ll> lpair;

ll dp[110][100010] = {};



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N,W;

    ll w[110], v[110];

    cin >> N >> W;

    rep(i,0,N){

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

    }

    rep(i,0,N+1){

        rep(j,0,100010){

            dp[i][j] = INF;

        }



    }

    dp[0][0] = 0;

    rep(i,0,N){

        rep(j,0,100010){

            if(j - v[i] >= 0){

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

            }else{

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

            }

        }

    }

    ll ans = 0;

    rep(i,0,100010){

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

            ans = i;

        }

    }

    print(ans);

}


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

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using lpair = pair<ll, ll>;

const ll MOD = 1e9+7;

const ll INF = 1e18;

#define rep(i,m,n) for(ll i=(m);i<(n);i++)

#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)

#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};

void print() {}

template <class H,class... T>

void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N,W;

    cin >> N >> W;

    ll w[110], v[110];

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

    ll dp[100010] = {};

    rep(i,0,100001) dp[i] = INF;

    dp[0] = 0;

    rep(i,0,N){

        rrep(j,N*1000,0){

            if(j - v[i] >= 0){

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

            }

        }

    }

    rrep(i,N*1000,0){

        if(dp[i] <= W){

            print(i);

            return 0;

        }

    }





    



}

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



using namespace std;

#define inf 0x3f3f3f3f3f3f3f3f

#define FASTIO cin.sync_with_stdio (0); cin.tie (0); cin.exceptions (cin.failbit); cout.tie(0);

typedef vector<int> vi;

typedef long long ll;

main(){

    FASTIO;

    ll N, W;

    cin >> N >> W;

    vector<ll> dp(123456, inf);

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

        ll w, v;

        cin >> w >> v;

        if (i == 0) dp[v] = w;

        else{

        for (ll valor = 123456 - v - 1; valor >= 0; valor--){

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

        }

        dp[v] = min(dp[v], (ll)w);

        }

    }

    for (ll i = 123455; i > -1; --i){

        if (dp[i] <= W){

            cout << i << '\n';

            return 0;

        }

    }

}

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



using namespace std;

#define inf 0x3f3f3f3f3f3f3f3f

#define FASTIO cin.sync_with_stdio (0); cin.tie (0); cin.exceptions (cin.failbit); cout.tie(0);

typedef vector<int> vi;

typedef long long ll;

main(){

    FASTIO;

    ll N, W;

    cin >> N >> W;

    vector<ll> dp(100009, inf);

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

        ll w, v;

        cin >> w >> v;

        if (i == 0) dp[v] = w;

        else{

        for (ll valor = 100009 - v - 1; valor >= 0; valor--){

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

        }

        dp[v] = min(dp[v], (ll)w);

        }

    }

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

        if (dp[i] <= W){

            cout << i << '\n';

            return 0;

        }

    }

}

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

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

#define ll long long

#define vi vector <ll> v

#define vii vector<pair<ll,ll>>v

#define pb push_back

#define mod 1000000007

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

#define while_ int t;cin>>t;while(t--)

#define vmax 100000

using namespace std;

 

 

 ll dp[101][vmax+1];

ll maxP(ll W, ll n, ll w[], ll v[])

{

  

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

  dp[0][i]=1e18;

  dp[0][0] = 0;

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

  {

      for(ll av=0;av<=vmax;av++)

      {

          if(v[an-1]>av) dp[an][av]=dp[an-1][av];

          else

          dp[an][av]=min(dp[an-1][av],w[an-1]+dp[an-1][av-v[an-1]]);

      }

  }

  ll ans=0;

  f(i,0,vmax+1)

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

   ans=i;

  return ans;

 

}

 

int main() {

    fastio

   

    ll n,W;

    cin>>n>>W;

    ll w[n],v[n];

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

    cout<<maxP(W,n,w,v);

   

}

// Optimized solution to the same problem (faster):
// #pragma GCC optimize("Ofast")

// #pragma GCC target("avx,avx2,fma")

// #pragma GCC optimization("unroll-loops")

#include<bits/stdc++.h>

#define ll long long

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

#define mod 998244353

#define mp make_pair

#define ff first

#define ss second

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

#define sc(a) scanf("%lld",&a)

#define pf printf

#define sz(a) (ll)(a.size())

#define psf push_front

#define ppf pop_front

#define ppb pop_back

#define pb push_back

#define pq priority_queue

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

 

using namespace std;

 

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    int n,wt;

    cin>>n>>wt;

    int w[n],v[n],sum=0;

    f(i,0,n)

        cin>>w[i]>>v[i],sum+=v[i];

    // cout<<sum<<"\n";

    ll dp[n+1][sum+1];

    f(i,0,n+1)

        dp[i][0]=0;

    f(i,0,sum+1)

        dp[0][i]=1e18;

    dp[0][0] = 0;

    f(i,1,n+1)

    {

        f(j,1,sum+1)

        {

            if(v[i-1]>j)

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

            else

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

        }

    }

    int ans=0;

    for(int j=sum;j>0;j--)

    {

        if(dp[n][j]<=wt)

        {

            // cout<<"Ent\n";

            ans=j;

            break;

        }

    }

    // cout<<dp[n][140]<<"\n";

    // f(i,0,n+1)

    // {

    //  f(j,0,sum+1)

    //      cout<<dp[i][j]<<' ';

    //  cout<<"\n";

    // }

    cout<<ans;

}

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

#define ll long long

#define max_sum 100000



using namespace std;



vector <ll> V;

ll dp[110][max_sum + 1];



int main() {

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

        dp[0][j] = INT_MAX;



    ll n, W;

    cin >> n >> W;

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

        ll weights, value;

        cin >> weights >> value;

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

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

            if(j - value >= 0)

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

        }

    }



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

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

            cout << i;

            return 0;

        }

    }

}


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

#define ll long long



using namespace std;



int main(){

    int n, W;

    cin >> n >> W;

    vector<ll> dp(100001, INT_MAX); //dp[i] min weight at value = i

    dp[0]=  0;

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

        int weights, value;

        cin >> weights >> value;



        for(int j = 100001 - value; j >= 0; j--) 

            dp[j + value] = min(dp[j + value], dp[j] + weights); 

    }



    int ans = 0;

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

        if(dp[i] <= W)

			ans = max(ans, i);



    cout << ans;



}


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

#define ll long long

#define max_sum 100000



using namespace std;



vector <ll> V;

ll dp[101][max_sum + 1];



int main() {

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

        dp[0][j] = INT_MAX;



    ll n, W;

    cin >> n >> W;

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

        ll weights, value;

        cin >> weights >> value;

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

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

            if(j - value >= 0)

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

        }

    }



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

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

            cout << i;

            return 0;

        }

    }

}


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

#define ll long long



using namespace std;



int main(){

    int n, W;

    cin >> n >> W;

    vector<ll> dp(100001, INT_MAX); //dp[i] min weight at value = i

    dp[0]=  0;

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

        int weights, value;

        cin >> weights >> value;



        for(int j = 100001 - value; j >= 0; j--) 

            dp[j + value] = min(dp[j + value], dp[j] + weights); 

    }



    int ans = 0;

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

        if(dp[i] <= W)

			ans = max(ans, i);



    cout << ans;



}


// Fastest known solution for this problem:
// Original C++ solution (slower):
// in the name of Allah

// Ya Ali!

#include <bits/stdc++.h>

using namespace std;



typedef long long ll ;

const ll maxn = 111111 ;

const ll INF = 1e18 ;



#define f first

#define s second



ll n , w1 , w[maxn] , v[maxn] , dp[110][maxn] , sum = 0 ;



int main()

{

 std::ios::sync_with_stdio(0) ;

 cin.tie(0) ;

 cout.tie(0) ;



 cin >> n >> w1 ;

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

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

    sum += v[i] ;

 }



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

  dp[0][i] = INF ;

 }



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

    for(int j = 0 ; j <= 1e5 + 20 ; j ++){

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

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

    }

 }



 ll ans = 0 ;

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

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

 }

 cout << ans ;



     return 0;

}


// Optimized solution to the same problem (faster):
// in the name of Allah

// Ya Ali!

#include <bits/stdc++.h>

using namespace std;



typedef long long ll ;

const ll maxn = 111111 ;

const ll INF = 1e18 ;



#define f first

#define s second



ll n , w1 , w[maxn] , v[maxn] , dp[110][maxn] , sum = 0 ;



int main()

{

 std::ios::sync_with_stdio(0) ;

 cin.tie(0) ;

 cout.tie(0) ;



 cin >> n >> w1 ;

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

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

    sum += v[i] ;

 }



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

  dp[0][i] = INF ;

 }



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

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

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

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

    }

 }



 ll ans = 0 ;

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

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

 }

 cout << ans ;



     return 0;

}


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

 *                                                                   

 *   |    |                        ,   .              ,--.,--.,--.,--.

 *   |    |    ,---..    ,,---.    |   |,---..   .      -||  ||  ||  |

 *   |    |    |   | \  / |---'    `---'|   ||   |       ||  ||  ||  |

 *   `    `---'`---'  `'  `---'      |  `---'`---'    `--'`--'`--'`--'

 *                                   `                                

**/

#include <bits/stdc++.h>

using namespace std;



long long n, w, wei[105], val[105];

long long dp[105][100005];



int main() {

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);



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

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



	cin >> n >> w;

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

		cin >> wei[i] >> val[i];

	}



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

		dp[0][i] = 1e14;

	}



	int ans = 0;

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

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

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

			if (j - val[i] >= 0) dp[i][j] = min(dp[i][j], dp[i - 1][j - val[i]] + wei[i]);

			if (j <= val[i]) dp[i][j] = min(dp[i][j], wei[i]);



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

		}

	}



	cout << ans << '\n';



	return 0;

}

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

using namespace std;



const int INF = 1e9 + 7;



int n, w, a[105], b[105];

long long dp[100005];

 

int main() {

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);



	cin >> n >> w;

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

		cin >> a[i] >> b[i];

	}



	fill(&dp[0], &dp[0] + 100001, INF);

	dp[0] = 0;

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

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

			if (j >= b[i]) dp[j] = min(dp[j], dp[j - b[i]] + a[i]);

		}

	}



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

		if (dp[i] <= w) {

			cout << i << '\n';

			break;

		}

	}



	return 0;

}

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

#define INF (1<<30)

#define MOD 1000000007

#define l_ength size

using ll = long long;

using namespace std;



ll dp[110][100100];

	

int main(){

	ll n, wc; cin >> n >> wc;

	vector<ll> w(n+1, 0);

	vector<ll> v(n+1, 0);

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

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

	}

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

		dp[0][i] = INF;

	}

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

		dp[i][0] = 0;

	}

	ll sum = 0;

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

		sum += v[i];

		for( ll j = 1; j < 100100; ++j ){

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

			if( j >= v[i] ){

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

			}

		}

	}

	/*

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

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

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

				cout << "∞ ";

			} else {

				cout << dp[i][j] << " ";

			}

		}

		cout << endl;

	}

	*/

	int ans = 0;

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

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

			ans = max(ans, i);

		}

	}

	cout << ans << endl;

	return 0;

}

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

#define INF (1<<30)

#define MOD 1000000007

#define l_ength size

using ll = long long;

using namespace std;



ll dp[105][100005];



int main(){

	int n; ll wmax;

	cin >> n >> wmax;

	vector<ll> v(n);

	vector<ll> w(n);

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

	ll vsm = accumulate( v.begin(), v.end(), 0ll );

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

		dp[i][0] = 0;

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

			dp[i][j] = INF;

		}

	}

	

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

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

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

			if( j >= v[i] && dp[i][j-v[i]] + w[i] <= wmax ){

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

			}

		}

	}

	ll ans = 0;

	for( ll j = vsm; j >= 0; --j ){

		if( dp[n][j] <= wmax ){

			ans = j;

			break;

		}

	}

	cout << ans << endl;

	return 0;

}

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

using namespace std;



// clang-format off

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

#define forn(i, x, y) for(int i = x; i < y; i++)

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



using ll = long long;

// clang-format on



const long long INF = 1LL << 60;

const int MAX_V = 100001;



int main()

{

  IOS;



  ll N, W;

  cin >> N >> W;

  vector<ll> w(N), v(N);

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



  vector<ll> dp(MAX_V, INF);

  dp[0] = 0;



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

  {

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

    {

      if (j >= v[i])

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

    }

  }



  ll res = 0;

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

  {

    if (dp[j] <= W)

      res = j;

  }

  cout << res << endl;



  return 0;

}


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

using namespace std;



// clang-format off

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

#define forn(i, x, y) for(int i = x; i < y; i++)

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



using ll = long long;

// clang-format on



const long long INF = 1LL << 60;



int main()

{

  IOS;



  ll N, W;

  cin >> N >> W;

  vector<ll> w(N), v(N);

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



  const ll sum_v = accumulate(v.begin(), v.end(), 0LL);



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

  dp[0] = 0;



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

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

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



  for (int i = sum_v; i >= 0; i--)

    if (dp[i] <= W)

    {

      cout << i << endl;

      break;

    }



  return 0;

}


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

#define ll long long

#define ull unsigned ll

#define ld long double

#define pll pair<ll, ll>

#define pii pair<int, int>

#define f first

#define se second

#define pb push_back

#define ft fflush(stdout)

 

 

using namespace std;

 

 

const int N = 1e5 + 123;

const int PLS = 3e5 + 123;

const int mod = 1e9 + 7;

const ll inf = 1e16;





ll n, a[N], b[N], w, dp[110][N];





int main() {

    ios_base::sync_with_stdio(NULL);

    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> w;

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

        cin >> a[i] >> b[i];

    dp[0][0] = 0;

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

        dp[0][i] = inf;

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

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

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

            if (j >= b[i])

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

        }

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

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

            return cout << i, 0;

}

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

#include<cstring> 

#include<iostream>

#include<algorithm>

using namespace std;

const int M=1200000;

int n,m,w[M],v[M],sum;long long dp[M];

int main(){

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

	dp[0]=0;

	for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]),sum+=v[i];

	for(int i=1;i<=sum;i++) dp[i]=1000000000ll*100ll+1ll;

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

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

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

	for(int i=sum;i>=0;i--) if(dp[i]<=m){

		printf("%d",i) ;break;

	}

	

}

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

 

#define ll long long

#define X first

#define Y second

#define MP make_pair

#define ld long double

 

using namespace std;

 

const int N = 5e5 + 123;

const ll mod = 1e9 + 7;



ll dp[N], res, was[N];

int n, maxw;



int main (){

	ios::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);



	cin >> n >> maxw;



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

		dp[i] = N * 1LL * N;



	was[0] = 1;

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

		ll x, y;

		cin >> x >> y;

		for(int j = 100000;j >= y;j--){

			if(!was[j - y])

				continue;

			was[j] = 1;

			dp[j] = min(dp[j], dp[j - y] + x);

		}

	}



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

		if(dp[i] <= maxw){

			res = i;

		}

	}



	cout << res;

}

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

#include<cstring> 

#include<iostream>

#include<algorithm>

using namespace std;

const int M=1200000;

int n,m,w[M],v[M],sum;long long dp[M];

int main(){

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

	dp[0]=0;

	for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]),sum+=v[i];

	for(int i=1;i<=sum;i++) dp[i]=1000000000ll*100ll+1ll;

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

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

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

	for(int i=sum;i>=0;i--) if(dp[i]<=m){

		printf("%d",i) ;break;

	}

	

}

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

#include <iomanip>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <ctime>

#include <string>

#include <stdio.h>

#include <set>

#include <map>

#include <algorithm>

#include <queue>

#include <vector>

#define ll long long

#define pb push_back

#define mp make_pair

#define f first

#define s second



using namespace std;



const int inf = 1e9 + 7;

const long long INF = 1e18 + 7;

const int maxn = 2e5 + 7;



ll n, s, w[maxn], a[maxn];

ll dp[maxn], mx;



int main(){

	ios_base::sync_with_stdio(NULL);

	cin.tie(0);

	cout.tie(0);

	cin >> n >> s;

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

		dp[i] = inf;

	dp[0] = 0;

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

		cin >> w[i] >> a[i];

		for (ll j = 100000; j >= 0; j--){

			if (dp[j] != inf && dp[j] + w[i] <= s){

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

			}

		}

	}

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

		if (dp[i] != inf)

			mx = max(mx, i);

	cout << mx;

	return 0;

} 

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

#include<cstring> 

#include<iostream>

#include<algorithm>

using namespace std;

const int M=1200000;

int n,m,w[M],v[M],sum;long long dp[M];

int main(){

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

	dp[0]=0;

	for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]),sum+=v[i];

	for(int i=1;i<=sum;i++) dp[i]=1000000000ll*100ll+1ll;

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

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

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

	for(int i=sum;i>=0;i--) if(dp[i]<=m){

		printf("%d",i) ;break;

	}

	

}

// Fastest known solution for this problem: