stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>



using namespace std;

typedef long long ll;



const int MAXN = 1e6 + 100;

const int inf = 0x3f3f3f3f;

ll n, k;

ll dp[MAXN];

ll w[MAXN];

ll v[MAXN];

ll ans;



int main(){

	scanf("%lld %lld", &n, &k);

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

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

	}

	memset(dp, inf, sizeof dp);

	dp[0] = 0;

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

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

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

	}

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

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

	}

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.0899938037910144x):
//submitting previously written code, to keep track of my progress. 

#include <iostream>

#include <vector>

#include <cmath>

#include <set>

#include <queue>

#include <map>

#include <cstdio>

#include <cstring>

#include <string>

#include <stack>

#include <algorithm>

#include <limits.h>

#include <bits/stdc++.h>

#define fw(x) freopen("x.txt","w",stdout)

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

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

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

#define mem(a,s) memset(a,s,sizeof a)

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

#define pf printf

#define sc scanf

#define ll long long

#define pii pair<int,int>

#define pll pair<ll,ll>

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

#define vii vector<int>

#define vll vector<ll>

#define vss vector<string>

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

#define pb push_back





using namespace std;





// moves



//int dx[]= {0,0,1,-1};/*4 side move*/

//int dy[]= {-1,1,0,0};/*4 side move*/

//int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/

//int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/

//int dx[]={1,1,2,2,-1,-1,-2,-2};/*knight move*/

//int dy[]={2,-2,1,-1,2,-2,1,-1};/*knight move*/





//big_mod



//ll bigmod(ll a,ll b,ll m)

//{if(b == 0) return 1%m;ll x = bigmod(a,b/2,m);x = (x * x) % m;if(b % 2 == 1) x = (x * a)% m;return x;}

//ll BigMod(ll B,ll P,ll M){ ll R=1%M; while(P>0) {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;} /// (B^P)%M



//ll getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1ll;}

//ll setBit1(ll num, int idx) {return num or (1ll<<idx);}

//ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}

//ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}



const int mod = 1000000007;



    int cost[101];

    int wt[101];

    ll dp[101][100001];

int main()

{

    fast;

    int n, w;

    cin>>n>>w;

    REP1(i, n) cin>>wt[i]>>cost[i];

    REP(i, n+1){

      REP(j, 100001){

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

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

        else{

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

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

        }

      }

    }

    ll ans = 0;

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

    cout<<ans<<'\n';

    return 0;

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

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#define LL long long

using namespace std;

LL n,m,dp[1000001],v[101],w[101],sum,ans; 

int main()

{

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

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

	{

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

		sum+=v[i];

	}

	memset(dp,127/3,sizeof dp);

	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--)

	{

		if(dp[i]<=m){

			ans=i;break;

		}

	}

	cout<<ans;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8556096011502903x):
//submitting previously written code, to keep track of my progress. 

#include <iostream>

#include <vector>

#include <cmath>

#include <set>

#include <queue>

#include <map>

#include <cstdio>

#include <cstring>

#include <string>

#include <stack>

#include <algorithm>

#include <limits.h>

#include <bits/stdc++.h>

#define fw(x) freopen("x.txt","w",stdout)

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

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

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

#define mem(a,s) memset(a,s,sizeof a)

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

#define pf printf

#define sc scanf

#define ll long long

#define pii pair<int,int>

#define pll pair<ll,ll>

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

#define vii vector<int>

#define vll vector<ll>

#define vss vector<string>

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

#define pb push_back





using namespace std;





// moves



//int dx[]= {0,0,1,-1};/*4 side move*/

//int dy[]= {-1,1,0,0};/*4 side move*/

//int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/

//int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/

//int dx[]={1,1,2,2,-1,-1,-2,-2};/*knight move*/

//int dy[]={2,-2,1,-1,2,-2,1,-1};/*knight move*/





//big_mod



//ll bigmod(ll a,ll b,ll m)

//{if(b == 0) return 1%m;ll x = bigmod(a,b/2,m);x = (x * x) % m;if(b % 2 == 1) x = (x * a)% m;return x;}

//ll BigMod(ll B,ll P,ll M){ ll R=1%M; while(P>0) {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;} /// (B^P)%M



//ll getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1ll;}

//ll setBit1(ll num, int idx) {return num or (1ll<<idx);}

//ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}

//ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}



const int mod = 1000000007;



    int cost[101];

    int wt[101];

    ll dp[101][100001];

int main()

{

    fast;

    int n, w;

    cin>>n>>w;

    REP1(i, n) cin>>wt[i]>>cost[i];

    REP(i, n+1){

      REP(j, 100001){

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

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

        else{

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

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

        }

      }

    }

    ll ans = 0;

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

    cout<<ans<<'\n';

    return 0;

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

using namespace std;

const int   N=1e2+10,M=1e5+10;

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

int main()

{

	long long n,m;

	cin>>n>>m;

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

	{

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

	}

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

		for(int j=0;j<=M;j++)f[i][j]=1e9+1;

	f[0][0]=0;

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

	{

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

		{

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

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



		}

	}

	long long ans=0;

	for(long long  j=1;j<=M;j++)

		if(f[n][j]<=m)ans=max(ans,j);

	cout<<ans<<endl;

   return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.5003424891514794x):
//submitting previously written code, to keep track of my progress. 

#include <iostream>

#include <vector>

#include <cmath>

#include <set>

#include <queue>

#include <map>

#include <cstdio>

#include <cstring>

#include <string>

#include <stack>

#include <algorithm>

#include <limits.h>

#include <bits/stdc++.h>

#define fw(x) freopen("x.txt","w",stdout)

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

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

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

#define mem(a,s) memset(a,s,sizeof a)

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

#define pf printf

#define sc scanf

#define ll long long

#define pii pair<int,int>

#define pll pair<ll,ll>

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

#define vii vector<int>

#define vll vector<ll>

#define vss vector<string>

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

#define pb push_back





using namespace std;





// moves



//int dx[]= {0,0,1,-1};/*4 side move*/

//int dy[]= {-1,1,0,0};/*4 side move*/

//int dx[]= {1,1,0,-1,-1,-1,0,1};/*8 side move*/

//int dy[]= {0,1,1,1,0,-1,-1,-1};/*8 side move*/

//int dx[]={1,1,2,2,-1,-1,-2,-2};/*knight move*/

//int dy[]={2,-2,1,-1,2,-2,1,-1};/*knight move*/





//big_mod



//ll bigmod(ll a,ll b,ll m)

//{if(b == 0) return 1%m;ll x = bigmod(a,b/2,m);x = (x * x) % m;if(b % 2 == 1) x = (x * a)% m;return x;}

//ll BigMod(ll B,ll P,ll M){ ll R=1%M; while(P>0) {if(P%2==1){R=(R*B)%M;}P/=2;B=(B*B)%M;} return R;} /// (B^P)%M



//ll getBit(ll num, int idx) {return ((num >> idx) & 1ll) == 1ll;}

//ll setBit1(ll num, int idx) {return num or (1ll<<idx);}

//ll setBit0(ll num, int idx) {return num & ~(1ll<<idx);}

//ll flipBit(ll num, int idx) {return num ^ (1ll<<idx);}



const int mod = 1000000007;



    int cost[101];

    int wt[101];

    ll dp[101][100001];

int main()

{

    fast;

    int n, w;

    cin>>n>>w;

    REP1(i, n) cin>>wt[i]>>cost[i];

    REP(i, n+1){

      REP(j, 100001){

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

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

        else{

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

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

        }

      }

    }

    ll ans = 0;

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

    cout<<ans<<'\n';

    return 0;

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

using namespace std;

const int N = 105;

const int V = 1e5 + 100;

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

long long dp[V];



int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);



	cin >> n >> we;



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

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

	}



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

		dp[j] = LLONG_MAX;

	}



	dp[0] = 0;

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

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

			if (dp[j] == LLONG_MAX) continue;

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

		}

	}



	int ans = 0 ;

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

		if (dp[i] > we) continue;

		ans = i;

		break;

	}



	cout << ans << '\n';



	return 0;

}


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

using namespace std;

const int N = 105;

const int V = 1e5 + 100;

const int W_MAX = 1e9 + 5;

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

int dp[V];



int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);



	cin >> n >> we;



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

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

	}



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

		dp[j] = W_MAX;

	}



	dp[0] = 0;

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

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

			if (dp[j] == W_MAX) continue;

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

		}

	}



	int ans = 0 ;

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

		if (dp[i] > we) continue;

		ans = i;

		break;

	}



	cout << ans << '\n';



	return 0;

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

#include<algorithm>

#define INF 100000000000

using namespace std;

typedef long long ll;

int n,W;

ll w[100],v[100];

ll dp[101][100001];

int main(){

  cin >> n >> W;

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

  for(int i=1;i<=100000;i++) dp[0][i]=INF;

  dp[0][0]=0;

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

    for(int j=0;j<=100000;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<=100000;i++){

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

  }

  cout << res << "\n";



  

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.0167870361616x):
#include<iostream>

#include<algorithm>

#include<climits>

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

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

#define scan(arg) cin>>arg

#define prin(arg) cout<<arg<<"\n"

#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"

using namespace std;

typedef long long ll;

const ll INF=1e+15;

int n;

ll W;

ll w[110],v[110];

ll dp[110][100010];

int main(){

  scan(n);scan(W);

  int sumv=0;

  rep(i,n){

    scan(w[i]);scan(v[i]);

    sumv+=v[i];

  }

  rep(j,sumv+1){

    dp[0][j]=INF;

  }

  rep1(i,n){

    rep(j,sumv+1){

      if(j<=v[i-1]){

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

      }

      else{

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

      }

    }

  }

  bool f=true;

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

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

      prin(j);

      f=false;

      break;

    }

  }

  if(f)prin(0);

  /* rep(i,n+1){

    rep(j,sumv+1){

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

    }

    prin('.');

    }*/



  



  

  return 0;

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

using namespace std;

#define endl '\n'

typedef long long ll;

const ll oo = 0x3f3f3f3f3f3f3f3f;



int main()

{

  ios_base::sync_with_stdio(0);

  cin.tie(0);

  

  ll n, w;

  cin >> n >> w;

  

  ll N = n * 5000 + 100;

  vector<ll> dp(N, oo);

  dp[0] = 0;

  

  for(ll i = 0, a, b; i < n; ++i)

  {

  	cin >> a >> b;

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

      if(dp[j] != oo && j + b < N)

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

  }

  

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

  {

  	if(dp[i] <= w)

    {

      cout << i << endl;

      return 0;

    }

  }

  

}


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

using namespace std;

#define endl '\n'

typedef long long ll;

const ll oo = 0x3f3f3f3f3f3f3f3f;



int main()

{

  ios_base::sync_with_stdio(0);

  cin.tie(0);

  

  ll n, w;

  cin >> n >> w;

  

  ll N = n * 1000 + 100;

  vector<ll> dp(N, oo);

  dp[0] = 0;

  

  for(ll i = 0, a, b; i < n; ++i)

  {

  	cin >> a >> b;

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

      if(dp[j] != oo)

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

  }

  

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

  {

  	if(dp[i] <= w)

    {

      cout << i << endl;

      return 0;

    }

  }

  

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

using namespace std;



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

	if (a > b) {

		a = b;

		return true;

	}

	return false;

}



const long INF = 1L << 60;



int weight[110];

int value[110];

long dp[2][110000];



int main(){

	int n, w;

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

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

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

	}

	for(int i = 1; i < 110000; i++) dp[0][i] = INF;

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

		int t = i % 2;

		for(int j = 0; j < 110000; j++) dp[t][j] = INF;

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

			chmin(dp[t][j], dp[!t][j]);

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

				chmin(dp[t][j], dp[!t][j-value[i-1]] + weight[i-1]);

		}

	}

	long ret = 0;

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

		if(dp[n%2][i] <= w) ret = i;

	printf("%ld", ret);

}


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

using namespace std;



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

	if (a > b) {

		a = b;

		return true;

	}

	return false;

}



const long INF = 1L << 60;



int weight[110];

int value[110];

long dp[110000];



int main(){

	int n, w, sum = 0;

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

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

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

		sum += value[i];

	}

	for(int i = 0; i <= sum; i++) dp[i] = INF;

	dp[0] = 0;

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

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

			chmin(dp[j+value[i]], dp[j] + weight[i]);

	long ret = 0;

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

		if(dp[i] <= w) ret = max(ret, (long)i);

	printf("%ld", ret);

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

#define endl '\n'

#define ll long long int

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

#define pb                    push_back

#define F                     first

#define S                     second

#define mp                    make_pair

#define clr(x)                x.clear()

#define MOD                   1000000007

#define itoc(c)               ((char)(((int)'0')+c))

#define vl                    vector<ll>

#define SZ(x)                 (x).size()

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

#define mid(s,e)              (s+(e-s)/2)

#define sv()                  ll t,n; scanf("%lld",&t);n=t; while(t--)

#define tcase()               ll t,n; cin>>t;n=t; while(t--)

#define iscn(num)             scanf("%d",&num);

#define scn(num)              scanf("%lld",&num);

#define scn2(num,num2)        scanf("%lld%lld",&num,&num2);

#define dbg(x)                cerr <<"( "<<#x << " = " << x << " )"<<endl

using namespace std;

const ll INF = 2e18 + 99;

typedef pair<ll,ll> Pair;

typedef vector<ll> vec;;

void FAST_IO();

void ara_read(vec &v,ll n);

////////////////////////



int main()

{

	ll n, knapsack ;

	scanf("%lld%lld",&n,&knapsack);

	/* now in this problem knapsack size is huge,

	 * so we can't use it as dp dimension. but here now value 

	 * is kinda small , we can this as dp dimension..

	 * we will use raw swapping to solve this dp problem */

	ll nax = n* 1000 + 10;

	vector< vector<ll > > dp(2,vector<ll> (nax,INF));

	bool prev=0, next =1;

	dp[0][0]=0 ;

	ll w, v ;

	

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

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

		for(int value =0 ; value < nax ; ++value){

			if(value<v){

				dp[next][value]= dp[prev][value];

			}else{

				dp[next][value]= min(dp[prev][value],dp[prev][value-v]+ w);

				

			}

		}

		swap(prev, next);

	}

	cerr << knapsack << endl;

	ll ans =0 ;

	for (int x = 0 ; x < nax ; ++x){

		if(dp[prev][x] <= knapsack){

			ans = x ;

			

		}

	}

	

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

    return 0;

}



void FAST_IO()

{

    // ios_base::sync_with_stdio(0);

    //cin.tie(NULL);

    //cout.tie(NULL);

    //cout.setf(ios::fixed);

    //cout.precision(2);



}

void ara_read(vec &v,ll n){

	ll temp;

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

		scanf("%lld",&temp);

		v.emplace_back(temp);

	}

	

}


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

#define ll long long int

using namespace std;



void min_self(ll &a , ll b){

	a=min(a,b);

}

const ll INF = 2e18 + 90 ;

int main(){

	

	ll  items, knapsack ;

	scanf("%lld%lld",&items,&knapsack);

	const ll nax = items * 1000 + 90 ;

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

	dp[0] = 0;

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

		ll weight,value;

		scanf("%lld%lld",&weight,&value);

		for(ll j = nax-1; j>=value ; --j){

			min_self(dp[j], dp[j-value]+weight);

		}

	}

	

	ll ans = INF;

	for(ll i=nax-1 ; i>=0 ; i--){

		if(dp[i]<=knapsack){

			ans=i;

			break ;

		}

	}

	

	

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

	return 0;

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

using namespace std;

using ll=long long;

using llu=unsigned long long;

#define mod 1000000007

#define mode 998244353

#define PI 3.14159265358979323846

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

#define mms(x,y) memset(x,y,sizeof(x))

#define pqm priority_queue<ll,vector<ll>,greater<ll>>

#define pb push_back

#define um unordered_map

#define pr pair

#define mm multimap

#define ms multiset

#define mp make_pair

#define vr vector

#define pq priority_queue

#define lb lower_bound

#define ub upper_bound

#define inf INT_MAX

#define ninf INT_MIN

#define ff first

#define ss second

#define gcd __gcd

int main()

{

    fast;

    ll t,n,m,i,j,k;

    cin>>n>>k;

    ll w[n],val[n];

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

    ll dp[n+1][100001];

    for(i=0;i<=n;i++)dp[i][0]=0;

    for(i=1;i<=100000;i++)dp[0][i]=inf;

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

    {

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

        {

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

            {

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

            }

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

        }

    }

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

    {

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

        {

            cout<<i;

            break;

        }

    }

}


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

using namespace std;

using ll=long long;

using llu=unsigned long long;

#define mod 1000000007

#define mode 998244353

#define PI 3.14159265358979323846

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

#define mms(x,y) memset(x,y,sizeof(x))

#define pqm priority_queue<ll,vector<ll>,greater<ll>>

#define pb push_back

#define um unordered_map

#define pr pair

#define mm multimap

#define ms multiset

#define mp make_pair

#define vr vector

#define pq priority_queue

#define lb lower_bound

#define ub upper_bound

#define inf INT_MAX

#define ninf INT_MIN

#define ff first

#define ss second

#define gcd __gcd

int main()

{

    fast;

    ll t,n,m,i,j,k;

    cin>>n>>k;

    ll w[n],val[n];

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

    ll dp[100001];

    dp[0]=0;

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

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

    {

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

        {

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

        }

    }

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

    {

        if(dp[i]<=k)

        {

            cout<<i;

            break;

        }

    }

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

}

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

}