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

 

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

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

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

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

#define ones(x) (ll) __builtin_popcount(x)

#define fs first

#define sc second

#define pb push_back

#define po pop_back

#define mp make_pair  

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

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

#define sor(a) sort( a.begin(), a.end() )

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

#define ller ios::sync_with_stdio(false);cin.tsie(nullptr);cout.tie(nullptr)

#define watch(x) cout << (#x) << " is #" << (x) <<"#" <<endl

#define PI 3.1415926535

using namespace std;

typedef long long ll;

typedef long double ld; 

typedef pair<ll,ll> ii ;

typedef vector<ll>  vi ;

typedef vector<ii> vii ;

const ll mod = 1e9+7;

const ll MAX = 1e5+5;

const ll inf = 1e18+7;



ll dp[MAX];

int main() {

  fastio;

  ll n,capac;

  cin>>n>>capac;

  f(i,0,MAX+1) dp[i]=inf;

  dp[0]=0;

  f(i,0,n){

    ll w,v;

    cin>>w>>v;

    af(j,MAX,v){

      if(dp[j-v]!=inf) dp[j]=min(dp[j],dp[j-v]+w);

    }

  }

  af(j,MAX,0){

  if(dp[j]<=capac){cout<<j<<"\n";break;}

  }

  return 0; 

}

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

using namespace std;

using ll=long long;

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

const int mod=1e9+7;

const int inf=1e9;

int w[M],v[M];

int dp[M][N];

 

int main(){

    int W,n;

    int val=0;

    cin>>n>>W;

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

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

        val+=v[i];

    }

    dp[0][0]=0;

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

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

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

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

            if(i>=v[j]){

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

            }

        }

    }

    

    int ans=0;

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

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

    }

    

    cout<<ans<<'\n';

    return 0;

}

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

//#pragma GCC optimize("Ofast")

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



using namespace std;



typedef long long ll;



//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>pb_ds;



#define IN freopen("in.txt","r",stdin)

#define OUT freopen("out.txt","w",stdout)

#define pi pair<int,int>

#define F first

#define S second

#define pb push_back

#define pp pop_back

#define mod 1000000007

#define pai acos(-1)

#define N 100000



ll Weight[N+5],Profit[N+5],dp[2][N+5];



int main ()

{

   ios_base::sync_with_stdio(false);

   cin.tie(NULL);

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

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

      cin>>Weight[i]>>Profit[i];

   }

   fill(dp[0],dp[0]+2*(N+5),INT_MAX*105);

   dp[(n+1)%2][0]=0;

   for(int i=n;i>=1;i--){

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

         ll op1=dp[(i+1)%2][p];

         ll op2=(p-Profit[i]>=0)?Weight[i]+dp[(i+1)%2][p-Profit[i]]:INT_MAX*105;

         dp[i%2][p]=min(op1,op2);

      }

   }

   int ans=0;

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

      if(dp[1][i]<=w){

         ans=max(ans,i);

      }

   }

   cout<<ans<<"\n";

   return 0;

}




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

using namespace std;

using ll=long long;

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

const int mod=1e9+7;

const int inf=1e9;

int w[M],v[M];

int dp[M][N];

 

int main(){

    int W,n;

    int val=0;

    cin>>n>>W;

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

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

        val+=v[i];

    }

    dp[0][0]=0;

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

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

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

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

            if(i>=v[j]){

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

            }

        }

    }

    

    int ans=0;

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

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

    }

    

    cout<<ans<<'\n';

    return 0;

}

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

using namespace::std;



const int MAX = 100000 + 5;

const int inf = 1e9 + 10;



int n;

int C;

int memo[MAX];



int main(){

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

	int sum = 0;

	for(int i = 1; i < MAX; i++) memo[i] = inf;

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

		int w, v;

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

		sum += v;

		for(int j = sum; j >= v; j--){

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

		}

	}

	int ans = 0;

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

		if(memo[i] <= C) ans = i;

	}

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

	return 0;

}

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

using namespace std;

using ll=long long;

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

const int mod=1e9+7;

const int inf=1e9;

int w[M],v[M];

int dp[M][N];

 

int main(){

    int W,n;

    int val=0;

    cin>>n>>W;

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

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

        val+=v[i];

    }

    dp[0][0]=0;

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

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

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

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

            if(i>=v[j]){

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

            }

        }

    }

    

    int ans=0;

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

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

    }

    

    cout<<ans<<'\n';

    return 0;

}

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



#include <bits/stdc++.h>

using namespace std;



const long long inf=1e18;



int main()

{       ios_base::sync_with_stdio(0);

        cin.tie(0);

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

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

        long n,W;

        cin>>n>>W;

        long v[n],w[n];



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

        {

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

        }



        long long dp[2][100007]; int mx=0; dp[0][0]=0; dp[1][0]=0;



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

        {   dp[0][i]=inf; dp[1][i]=inf;   }



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

        {

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

            {

                if(j%2==0){

                    if(i>=v[j] ) { if(dp[1][i-v[j] ] !=inf ) dp[0][i]=min( min(dp[1][i],dp[0][i]),dp[1][i-v[j]]+w[j] ); }



                                            {dp[0][i]=min(dp[0][i],dp[1][i]) ; }

                                            if(dp[0][i]!=inf && dp[0][i]<=W ) mx=max(i,mx);

                }

                else{

                    if(i>=v[j] ) { if(dp[0][i-v[j] ] !=inf ) dp[1][i]=min(min(dp[0][i],dp[1][i]),dp[0][i-v[j]]+w[j] ); }



                                            { dp[1][i]=min(dp[1][i],dp[0][i]) ; }

                                            if(dp[1][i]!=inf && dp[1][i]<=W ) mx=max(i,mx);

                }



            }

        }



        cout<<mx<<endl;



    return 0;

}


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

 using namespace std;

#define ll long long

int main(){

    int n,w;

    cin>>n>>w;

    ll a[2][n],dp[n*1000+1];

    for(int i=0;i<n;i++)cin>>a[0][i]>>a[1][i];

    for(int i=0;i<=n*1000;i++) dp[i]=INT_MAX;

    ll mx=0;

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

    {  

        for(ll j=n*1000;j>=1;j--){

            if(j>a[1][i] && dp[j-a[1][i]]!=INT_MAX ){ dp[j]=min(dp[j],dp[j-a[1][i]]+a[0][i]); }

            else if(j==a[1][i] ) dp[j]=min(dp[j],a[0][i]); 

                if( dp[j]!=INT_MAX && dp[j]<=w)  mx=max(j,mx);

            

        }

    }

    cout<<mx<<endl;

    return 0;

}

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

using namespace std;

typedef long long ll;

const ll inf = 1e15;

typedef pair<int,int> ii;

typedef vector<int> vi;



ll W[110],V[110];

ll dp[110][(int)1e5+10];



int main(){

	ll n,w;

	cin>>n>>w;

	ll max_val=0;

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

		cin>>W[i]>>V[i];

		max_val+=V[i];



	}

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

			dp[0][i]=inf;

	}

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

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

			if(j>=V[i]){

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

			}else{

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

			}

			

		}

	}



	int ans=0;

	for(int v=max_val;v>=0 && !ans;v--){

		if(dp[n][v]<=w){

			ans=v;

		}

	}

	cout<<ans;

	



	return 0;

}

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

using namespace std;

typedef long long ll;

const ll inf = 1e15;

typedef pair<int,int> ii;

typedef vector<int> vi;



const int max_item_cnt=100+10;

const int max_value_sum=1e5+10;

ll W[max_item_cnt],V[max_item_cnt];

ll dp[max_value_sum]; 

// dp[i] - min sum of weights with i value

 

int main(){

	ll n,w;

	cin>>n>>w;

	ll max_val=0;

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

		cin>>W[i]>>V[i];

		max_val+=V[i];

	}

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

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

		for(int j=max_val;j>=V[i];j--){

			dp[j]=min(dp[j-V[i]]+W[i],dp[j]);

		}

	}

	ll ans=0;

	//ans - max v such as dp[v]<=w

	for(int v=max_val;v>=0 && !ans;v--){

		if(dp[v]<=w){

			ans=v;

		}

	}

	cout<<ans;

 

	return 0;

}

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

using namespace std;

typedef long long ll;

const ll inf = 1e15;

typedef pair<int,int> ii;

typedef vector<int> vi;

const int max_item_cnt=100+10;

const int max_value_possible=1e5+10;

ll W[max_item_cnt],V[max_item_cnt];

ll dp[max_item_cnt][max_value_possible];//dp[i][j]-min weight to get at least j space from 1-th to i-th element

bool sol[max_item_cnt];

int main(){

	ll n,w;

	cin>>n>>w;

	ll max_val=0;

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

		cin>>W[i]>>V[i];

		max_val+=V[i];

 

	}

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

			dp[0][i]=inf;

	}

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

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

			if(j>=V[i]){

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

			}else{

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

			}

			

		}

	}

	int ans=0;

	for(int v=max_val;v>=0 && !ans;v--){

		if(dp[n][v]<=w){

			ans=v;

		}

	}

	int val=ans;

	for(int i=n;i>=1;i--){

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

			continue;

		}

		sol[i]=true;

		val-=V[i];

	}



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

		//cout<<sol[i]<<" ";

	}

	//cout<<endl;

	cout<<ans;

	

 

	return 0;

}

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

using namespace std;

typedef long long ll;

const ll inf = 1e15;

typedef pair<int,int> ii;

typedef vector<int> vi;



const int max_item_cnt=100+10;

const int max_value_sum=1e5+10;

ll W[max_item_cnt],V[max_item_cnt];

ll dp[max_value_sum]; 

// dp[i] - min sum of weights with i value

 

int main(){

	ll n,w;

	cin>>n>>w;

	ll max_val=0;

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

		cin>>W[i]>>V[i];

		max_val+=V[i];

	}

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

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

		for(int j=max_val;j>=V[i];j--){

			dp[j]=min(dp[j-V[i]]+W[i],dp[j]);

		}

	}

	ll ans=0;

	//ans - max v such as dp[v]<=w

	for(int v=max_val;v>=0 && !ans;v--){

		if(dp[v]<=w){

			ans=v;

		}

	}

	cout<<ans;

 

	return 0;

}

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

using namespace std;

typedef long long ll;

const ll inf = 1e15;

typedef pair<int,int> ii;

typedef vector<int> vi;

const int max_item_cnt=100+10;

const int max_value_possible=1e5+10;

ll W[max_item_cnt],V[max_item_cnt];

ll dp[2][max_value_possible];//dp[i][j]-min weight to get at least j space from 1-th to i-th element

bool sol[max_item_cnt];

int main(){

	ll n,w;

	cin>>n>>w;

	ll max_val=0;

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

		cin>>W[i]>>V[i];

		max_val+=V[i];

 

	}

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

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

	}

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

		int t = i%2;

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

			if(j>=V[i]){

				dp[t][j]=min(dp[!t][j],dp[!t][j-V[i]]+W[i]);

			}else{

				dp[t][j]=dp[!t][j];

			}

			

		}

	}

	int ans=0;

	for(int v=max_val;v>=0 && !ans;v--){

		if(dp[n%2][v]<=w){

			ans=v;

		}

	}

	cout<<ans;

	

	return 0;

}

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

using namespace std;

typedef long long ll;

const ll inf = 1e15;

typedef pair<int,int> ii;

typedef vector<int> vi;



const int max_item_cnt=100+10;

const int max_value_sum=1e5+10;

ll W[max_item_cnt],V[max_item_cnt];

ll dp[max_value_sum]; 

// dp[i] - min sum of weights with i value

 

int main(){

	ll n,w;

	cin>>n>>w;

	ll max_val=0;

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

		cin>>W[i]>>V[i];

		max_val+=V[i];

	}

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

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

		for(int j=max_val;j>=V[i];j--){

			dp[j]=min(dp[j-V[i]]+W[i],dp[j]);

		}

	}

	ll ans=0;

	//ans - max v such as dp[v]<=w

	for(int v=max_val;v>=0 && !ans;v--){

		if(dp[v]<=w){

			ans=v;

		}

	}

	cout<<ans;

 

	return 0;

}

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

#define ll long long int

using namespace std;

#define ar array





int main()

{

	//#ifndef ONLINE_JUDGE

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

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

	//#endif

	

	//int t;

	//cin>>t;

	//while(t--)

	{

		int n,w;

		cin>>n>>w;

		int a[n][2];

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

		{

			cin>>a[i][0]>>a[i][1];

		}

		ll dp[100000+1];

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

		dp[0]=0;

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

		{

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

			{

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

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

			}

		}

		ll ans=0;

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

		{

			if(dp[i]<=w)

			{

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

			}

		}

		cout<<ans<<'\n';

		

		

	}

		

}


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

#define ll long long int

using namespace std;

#define ar array

#define pb push_back



const int mxn=1e5+2;

ll dp[mxn];



int main()

{

	// #ifndef ONLINE_JUDGE

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

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

	// #endif

	

	//int t;

	//cin>>t;

	//while(t--)

	{

		int n,w;

		cin>>n>>w;

		ll a[n][2];

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

		{

			cin>>a[i][0]>>a[i][1];

		}

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

		dp[0]=0;

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

		{

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

			{

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

				{

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

				}

			}

		}

		int ans=0;

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

		{

			if(dp[i]<=w)

			{

				ans=max(ans,i);

			}

		}

		cout<<ans<<'\n';

		

	}

		

}


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

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

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

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

#define read(x) scanf("%d",&x)

#define read2(x,y) scanf("%d%d",&x,&y)

#define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define readll(x) scanf("%lld",&x)

#define mst(a,b) memset(a,b,sizeof(a))

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

#define pb push_back

#define lowbit(x) x&-x

#define lc rt<<1

#define rc rt<<1|1

#define ls lc,l,m

#define rs rc,m+1,r

#define dbg(x) cout<<' '<<#x<<" = "<<x<<endl;

#define dbg2(x,y) cout<<' '<<#x<<" = "<<x<<", "<<#y<<" = "<<y<<endl;

#define dbg3(x,y,z) cout<<' '<<#x<<" = "<<x<<", "<<#y<<" = "<<y<<", "<<#z<<" = "<<z<<endl;

const int INF =0x3f3f3f3f;

const int mod = 1e9+7;

const double eps=1e-8;

const int N = 2e5+5;

int dir[4][2]={0,1,0,-1,1,0,-1,0};

int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

int c[N],w[N];

ll dp[N];

int main(){

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

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

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

	int n,W;

	read2(n,W);

	int totv = 0;

    fe(i,1,n)read2(c[i],w[i]),totv+=w[i];

    mst(dp,0x3f);

    dp[0] = 0;

    fe(i,1,n){

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

				//value =j ,use min cost

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

    	}

    }

    int res;

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

        if(dp[i] <= W){

			res = i;

			break;

        }

    }

    cout<<res<<endl;









	return 0;

}


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

#include<cstdio>

#define maxn 110

using namespace std;

int n,W,sum;

int w[maxn],v[maxn],f[100010];

int main(){

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

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

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

		sum+=v[i];

	}

	for(int i=1;i<=sum;i++)f[i]=1000000001;

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

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

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

		}

	}

	int ans=0;

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

		if(f[i]<=W){

			ans=i;

			break;

		}

	}

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

	return 0;

} 

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

using namespace std;



#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define eb emplace_back



typedef long long ll;

typedef pair<int,int> ii;

typedef vector< pair<int,int> > vii;

const ll INF = 0x3f3f3f3f3f3fef;



const int V = 1e5+2;

const int N = 102;



ll dp[V];

ll p[N];

ll v[N];

ll n,w;

 

int main() {

    ios_base::sync_with_stdio(false);

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



    cin >> n >> w;

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

    

    dp[0] = 0;

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

        for(ll j = V-1; j-v[i] >= 0; j--)

            if(dp[j-v[i]] != INF) dp[j] = min(dp[j], dp[j-v[i]]+p[i]);



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

        if(dp[i] <= w) { cout << i << endl; return 0; }





    return 0;

}




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

#include<cstdio>

#define maxn 110

using namespace std;

int n,W,sum;

int w[maxn],v[maxn],f[100010];

int main(){

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

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

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

		sum+=v[i];

	}

	for(int i=1;i<=sum;i++)f[i]=1000000001;

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

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

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

		}

	}

	int ans=0;

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

		if(f[i]<=W){

			ans=i;

			break;

		}

	}

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

	return 0;

} 

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

#include<string.h>

#include<time.h>

#include<math.h>

#include<stdlib.h>

#include<iostream>

#include<iomanip>

#include<utility>

#include<algorithm>

#include<stack>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define fi first

#define sec second

#define pb push_back

#define mp make_pair

#define rep(a,b,c) for(int a=1;a<=b;a+=c)

#define repp(a,b,c,d) for(int a=b;a<=c;a+=d)



const double PI=acos(-1);

const double EPS=1e-12;

const int MOD=1e9+7;

const int INF=1<<30;





using namespace std;



int maxx[100005];



int main(){

	//ios::sync_with_stdio(false);cin.tie(NULL);	cout.tie(NULL);

	int in,n,t,w;

	rep(i,100000,1){

		maxx[i]=INF;

	}

	cin>>in>>n;

	rep(i,in,1){

		cin>>t>>w;

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

			maxx[j]=min(maxx[j],maxx[j-w]+t);

		}

	}

	int res=0;

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

		if(maxx[i]<=n){

			res=i;

			break;

		}

	}

	cout<<res<<endl;

	return 0;

}




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

#include<cstdio>

#define maxn 110

using namespace std;

int n,W,sum;

int w[maxn],v[maxn],f[100010];

int main(){

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

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

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

		sum+=v[i];

	}

	for(int i=1;i<=sum;i++)f[i]=1000000001;

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

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

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

		}

	}

	int ans=0;

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

		if(f[i]<=W){

			ans=i;

			break;

		}

	}

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

	return 0;

} 

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

using ll = long long;



#define MAX_W ((ll)1e9)

#define MAX_N (100)

#define MAX_V (1000)

int main(){

	std::cin.tie(0);

	std::ios::sync_with_stdio(false);



	int N, W;

	std::cin >> N >> W;

	std::vector<ll> val(N), wei(N), dp(MAX_V*MAX_N+10, (ll)1e12+1);

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

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

	}



	ll ans = 0;

	dp[0] = 0;

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

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

			dp[v] = std::min( dp[v], dp[v - val[i]] + wei[i] );

			if( dp[v] <= W )

				ans = std::max(ans, (ll) v );

		}

	}



	std::cout << ans << '\n';

	return 0;

}

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

#include<cstdio>

#define maxn 110

using namespace std;

int n,W,sum;

int w[maxn],v[maxn],f[100010];

int main(){

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

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

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

		sum+=v[i];

	}

	for(int i=1;i<=sum;i++)f[i]=1000000001;

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

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

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

		}

	}

	int ans=0;

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

		if(f[i]<=W){

			ans=i;

			break;

		}

	}

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

	return 0;

} 

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

#define ll long long

#define ld long double

#define ull unsigned ll

#define ioi exit(0);

 

#define f first

#define s second

 

#define inf (ll)1e18 + 7

 

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

 

#define mp(x,y) make_pair(x,y)

 

#define lb(x) lower_bound(x)

#define ub(x) upper_bound(x)

 

#define pb push_back

#define ppb pop_back

 

#define bitcoin __builtin_popcount

 

#define endl "\n"

 

#define in(x) insert(x)

 

#define sz(x) (int)x.size()

 

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

 

#define pw2(x) (1ll<<x) //2^x

 

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

 

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

 

#define UpdateRandom srand (time(NULL));

 

using namespace std;

 

const int N = (int)5e5 + 7, MOD = (int)1e9 + 7;



ll n,W;

ll w[N],v[N],dp[N];

bool was[N];

int main(){

		

	NFS



	cin >> n >> W;

	

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

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

	}

	

	memset(dp,-1,sizeof(dp));

	

	dp[0]=0;

	

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

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

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

				was[j]=1;

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

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

			}

		}

	}

	

	ll ans=0;

	

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

		if(was[i] && dp[i]<=W){

			ans=i;

			break;

		}

	}



	cout << ans << endl;

	

	//cout << dp[W] << endl;

	

	ioi

}

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

#include<cstdio>

#define maxn 110

using namespace std;

int n,W,sum;

int w[maxn],v[maxn],f[100010];

int main(){

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

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

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

		sum+=v[i];

	}

	for(int i=1;i<=sum;i++)f[i]=1000000001;

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

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

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

		}

	}

	int ans=0;

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

		if(f[i]<=W){

			ans=i;

			break;

		}

	}

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

	return 0;

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

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

#include<cstdio>

#define maxn 110

using namespace std;

int n,W,sum;

int w[maxn],v[maxn],f[100010];

int main(){

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

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

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

		sum+=v[i];

	}

	for(int i=1;i<=sum;i++)f[i]=1000000001;

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

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

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

		}

	}

	int ans=0;

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

		if(f[i]<=W){

			ans=i;

			break;

		}

	}

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

	return 0;

} 

// Fastest known solution for this problem: