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

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int, int> pi;

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

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

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

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

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define endl '\n'



ll dp[100005];



int main(){

	ios_base::sync_with_stdio(false);

	cin.tie(0);

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

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

	int n;

	ll w;

	cin >> n >> w;

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

	dp[0] = 0;

	rep(i, n){

		ll a;

		int b;

		cin >> a >> b;

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

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

		}

	}

	int ans;

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

	cout << ans << endl;

	return 0;

}

/*

Things to look out for:

	- Integer overflows

	- Array bounds

	- Special cases

Be careful!

*/


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

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef pair<int, int> pi;

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

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

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

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

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define endl '\n'



ll dp[100005];



int main(){

	ios_base::sync_with_stdio(false);

	cin.tie(0);

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

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

	int n;

	ll w;

	cin >> n >> w;

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

	dp[0] = 0;

	repn(i, 1, n + 1){

		ll a;

		int b;

		cin >> a >> b;

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

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

		}

	}

	int ans = 0;

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

	cout << ans << endl;

	return 0;

}

/*

Things to look out for:

	- Integer overflows

	- Array bounds

	- Special cases

Be careful!

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

using namespace std;

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

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

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

typedef long long ll;

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

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

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

#define F first

#define S second 

#define pb(n) push_back(n)

const int N=1e5+6;

const ll M=1e9+7;



int main()

{

	int n,w;

	scn(n);scn(w);

	ll dp[n+1][N];

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

	{

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

			dp[i][j]=M;

	}



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

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

	// problem

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

	{

		int wt,val;

		scn(wt);scn(val);

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

			dp[i][val]=wt;

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

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

		{

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

			if(j>=val)

			{

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

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

			}

		}

	}

	ll ans=0;

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

	{

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

		{			

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

			ans=i;

			break;

		}

	}

	lpri(ans);

}

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

using namespace std;

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

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

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

typedef long long ll;

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

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

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

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

#define F first

#define S second 

#define pb push_back

const int N=1e5+5;

// const ll M = 998244353;

const ll M=1e9+7;

const ll inf=1e18;



int dp[N]; 



int main()

{

	var(n);var(w);

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

		dp[i] = M;

	rep(i,0,n)

	{

		var(wt);

		var(val);

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

		{			

			if(dp[j]!=M)

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

		}

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

		

	}

	int ans = 0;

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

	{

		int wt = dp[i];

		if(wt<=w)

		{

			ans = i;

			break;

		}

	}

	pri(ans);

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

using namespace std;



#define lli long long int

#define pb push_back





main()

{

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

    cin>>n>>c;

    lli w[n],v[n];

    lli dp[100001];



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

    {

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

    }

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

    {

        dp[i] = c+1;

    }

    dp[0] = 0;

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

    {

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

        {

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

            {

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

            }

        }

    }



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

    {

        if(dp[i]<=c)

        {

            cout<<i;

            break;

        }

    }

}


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

using namespace std;



#define lli long long int

#define pb push_back

#define f first

#define sec second



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

{

    return i.sec <= j.sec;

}



main()

{

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

    vector<pair<lli,lli>> v;



    cin>>n>>cap;



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

    {

        cin>>a>>b;

        v.pb({b,a});

        sum += b;

    }



    lli dp[sum+1];

    dp[0] = 0;



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

    {

        dp[i] = cap+1;

    }



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

    {

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

        {

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

            {

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

            }

        }

    }



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

    {

        if(dp[i]<=cap)

        {

            cout<<i;

            return 0;

        }

    }

}
// Slower C++ solution:
/*for better*/

#include<bits/stdc++.h>

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

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

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

#define endl '\n'

#define ll long long int

#define ff first

#define ss second

#define pb push_back

#define mod 1000000007

#define M 998244353

#define inf 1e9+10

using namespace std;



ll dp[105][100005];



int main()

{

    fast; 

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

    cin>>n>>mx;

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

    f(i,1,n+1)

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

    

    f(i,0,n+1)

    	dp[i][0]=0;

    f(j,1,m)

    	dp[0][j]=inf;



    f(i,1,n+1)

    {

    	f(j,1,m)

    	{

    		if(j>=v[i])

    		{

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

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

    			{

    				dp[i][j]=x;

    				if(x<=mx)

    					ans=max(ans,j);

    			}

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

    		}

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

    	}

    }

    cout<<ans;

}


// Faster C++ solution for the same problem (measured speedup: 2.101646619321786x):
/*for better*/

#include<bits/stdc++.h>

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

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

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

#define endl '\n'

#define ll long long int

#define ff first

#define ss second

#define pb push_back

#define mod 1000000007

#define M 998244353

#define inf 1e9+10

using namespace std;



ll dp[100005];



int main()

{

    fast; 

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

    cin>>n>>mx;

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

    f(i,1,n+1)

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

    

    dp[0]=0;

    f(j,1,m)

    	dp[j]=inf;



    f(i,1,n+1)

    {

    	fr(j,m-1,1)

    	{

    		if(j>=v[i])

    		{

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

    			if(dp[j]>x)

    			{

    				dp[j]=x;

    				if(x<=mx)

    					ans=max(ans,j);

    			}

    		}

    	}

    }

    cout<<ans;

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



using namespace std;



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

#define mod 1000000007

#define endl "\n"

typedef long long ll;

 

int main(){ 

	

	FAST_IO;

   

	int n,W;

	cin>>n>>W;



	int V = 100007;



	ll w[n],v[n];



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

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

	}



	ll dp[n+1][V];

	ll inf = 1e10;



	fill(dp[0],dp[n+1],inf);



	dp[0][0] = 0;



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

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

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

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

			}

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

		}

	}



	ll ans = 0;

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

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

			ans = i;

	}



	cout<<ans<<endl;



}

 

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



using namespace std;



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

#define mod 1000000007

#define endl "\n"

typedef long long ll;

 

int main(){ 

	

	FAST_IO;

   

	int n,W;

	cin>>n>>W;



	int V = 100007;



	ll w[n],v[n];



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

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

	}



	ll dp[V];

	ll inf = 1e10;



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

		dp[i] = inf;

	}



	dp[0] = 0;



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

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

			if(j>=v[i])

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

		}

	}



	ll ans = 0;

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

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

		if(dp[i] <= W)

			ans = i;

	}



	cout<<ans<<endl;



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

#define ll long long

using namespace std;

const int N=1e5+5;

int a,b,n,m,ans=-1;

ll dp[N];

int main()

{

	cin>>n>>m;

	for(int i=0;i<N;i++)dp[i]=100000000000000;

	dp[0]=0;

	while(n--)

	{

		cin>>a>>b;

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

		{

			if(dp[j-b]+a>m)continue;

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

			ans=max(ans,j);

		}

	}

	cout<<ans;

	return 0;

}

/*

3 8

3 30

4 50

5 60

*/

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

using namespace std;

const int N=1e5+5;

int dp[N],n,m;

bool can[N];

int main()

{

	for(int i=1;i<N;++i)dp[i]=1e9+7;

	cin>>n>>m;

	can[0]=true;

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

	{

		int x,y;

		cin>>x>>y;

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

		{

			if(can[j-y]&&dp[j-y]+x<=m)

			{

				can[j]=true;

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

			}

		}

	}

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

	{

		if(can[i])

		{

			cout<<i<<endl;

			return 0;

		}

	}

	return 0;

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

#pragma GCC optimize "03"

using namespace std;



#define int long long int

#define pb push_back

#define pii pair<int,int>

#define fi first

#define se second

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

#define dbg(x) { cerr<<"> "<<#x<<": "<<x<< endl; }

#define dbg2(x,y) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<endl; }

#define dbg3(x,y,z) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<" , "<<#z<<": "<<z<<endl; }

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

#ifndef LOCAL

#define endl '\n'

#endif



const int inf = INT_MAX;

const int MOD = 1e9 + 7;

const int N = 105;



int w[N], v[N];

int dp[N][100005];



signed main(){

    IOS;

    int n, k;

    cin >> n >> k;

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

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

    }

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

        dp[0][i] = inf;

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

        for (int j = 1; j < 100005; 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]);

        }

    }

    int ans = 0;

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

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

    cout << ans << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.9956994940728445x):
// Optimised solution (Saves space)

// Converted matrix to an array

#include "bits/stdc++.h"

#pragma GCC optimize "03"

using namespace std;



#define int long long int

#define pb push_back

#define pii pair<int,int>

#define fi first

#define se second

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

#define dbg(x) { cerr<<"> "<<#x<<": "<<x<< endl; }

#define dbg2(x,y) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<endl; }

#define dbg3(x,y,z) { cerr<<"> "<<#x<<": "<<x<<" , "<<#y<<": "<<y<<" , "<<#z<<": "<<z<<endl; }

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

#ifndef LOCAL

#define endl '\n'

#endif



const int inf = INT_MAX;

const int MOD = 1e9 + 7;

const int N = 105;



int w[N], v[N];

int dp[100005];



signed main(){

    IOS;

    int n, k;

    cin >> n >> k;

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

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

    }

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

        dp[i] = inf;

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

        // Reverse loop

        for (int j = 100004; j >= 1; j--) {

            if (j >= v[i])

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

        }

    }

    int ans = 0;

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

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

    cout << ans << endl;

    return 0;

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

using namespace std;



#define y1 as214

#define ii pair < int , ll >

#define iii pair < int , ii >

#define iv pair < ii , ii >



#define fi first

#define se second

#define fr front()

#define pb push_back



#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)

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



#define ll long long

#define oo INT_MAX



/// dp[i][j] là trọng lượng nhỏ nhất có thể được khi xét i vât đầu tiên và tổng giá trị của i vật đó là j.



const int N = 1e2 + 5;

const int M = 1e5 + 5;

ll n , w;

ll W[N] , V[N];

ll dp[N][M];



int main()

{

    //freopen("E.inp","r",stdin);

    cin >> n >> w;

    FOR(i , 1 , n)

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

    FOR(i , 0 , n)

        FOR(j , 1 , 1e5)

            dp[i][j] = 1e18;

    dp[0][0] = 0;

    FOR(i , 1 , n)

        FOR(j , 1 , 1e5)

        {

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

                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 = 1e5 ;  i >= 1 ; i--)

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

    {

        cout << i;

        exit(0);

    }

}


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

using namespace std;



#define y1 as214

#define ii pair < int , int >

#define iii pair < int , ii >

#define iv pair < ii , ii >



#define fi first

#define se second

#define fr front()

#define pb push_back

#define t top()



#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)

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

#define FORD(i , x , n) for(int i = x ; i >= n ; --i)



#define ll long long

#define oo 1e17

#define int long long



const int N = 1e2 + 5;

const int VAL = 1e5 + 5;

int n , W;

int w[N] , v[N];

int dp[N][VAL];



/// dp[i][j] là trọng lượng tối thiếu để với i cái ba lô đầu có thể lấy được các vật có tổng = j.



main()

{

    //freopen("D.inp","r",stdin);

    ios::sync_with_stdio(0);

    cin.tie(0);

    cin >>  n >> W;

    FOR(i , 1 , n)

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

    dp[0][0] = 0;

    FOR(i , 1 , 1e5)

        dp[0][i] = 1e9 + 7;

    FOR(i , 1 , n)

    {

        FOR(j , 1 , 1e5)

        {

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

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

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

        }

    }

    FORD(i , 1e5 , 0)

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

        {

            cout << i;

            exit(0);

        }

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

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

ll n,W;

int w[100+10],v[100+10];

int dp[100+10][100000+10];

int main()

{

    cin>>n>>W;

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

    fill(dp[0],dp[0]+100000+1,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;

    return 0;

}

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

 

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

#define ll long long

#define ff first

#define ss second

 

const int maxn=105 ;

const int maxv=1005 ;

const int inf=1e9+10 ;

 

using namespace std ;

 

ll dp[maxn*maxv] ;

pair<ll,ll> v[maxn] ;

int ans ;

 

int main()

{

  lp(i,1,maxn*maxv) dp[i]=inf ;

  dp[0]=0;

 

  int n, w ;

 

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

  lp(i,0,n) scanf("%lld%lld", &v[i].ff, &v[i].ss) ;

 

  lp(i,0,n)

  {

    for(int j=ans+v[i].ss ; j >= v[i].ss ; j -- )

    {

      if(dp[ j-v[i].ss ] + v[i].ff <= w )

      {

        dp[j] = min(dp[j] , dp[ j-v[i].ss ] + v[i].ff ) , ans=max(ans,j) ;

      }

    }

  }

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

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

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

ll n,W;

int w[100+10],v[100+10];

int dp[100+10][100000+10];

int main()

{

    cin>>n>>W;

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

    fill(dp[0],dp[0]+100000+1,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;

    return 0;

}

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



using namespace std;





int main()

{

	int n, W;

	cin >> n >> W;



	vector<int> w(n + 1), v(n + 1);



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

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



	int V = *max_element(v.begin(), v.end()) * n;

	vector<vector<int>> dp(n + 1, vector<int>(V + 1, W + 1));





	dp[0][0] = 0;



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

	{

		for(int j = 0; j <= V; 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 = V; i > -1; i--)

	{

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

		{

			cout << i << endl;

			return 0;

		}

	}

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

 

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

#define ll long long

#define ff first

#define ss second

 

const int maxn=105 ;

const int maxv=1005 ;

const int inf=1e9+10 ;

 

using namespace std ;

 

ll dp[maxn*maxv] ;

pair<ll,ll> v[maxn] ;

int ans ;

 

int main()

{

  lp(i,1,maxn*maxv) dp[i]=inf ;

  dp[0]=0;

 

  int n, w ;

 

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

  lp(i,0,n) scanf("%lld%lld", &v[i].ff, &v[i].ss) ;

 

  lp(i,0,n)

  {

    for(int j=ans+v[i].ss ; j >= v[i].ss ; j -- )

    {

      if(dp[ j-v[i].ss ] + v[i].ff <= w )

      {

        dp[j] = min(dp[j] , dp[ j-v[i].ss ] + v[i].ff ) , ans=max(ans,j) ;

      }

    }

  }

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

}

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



using namespace std;





int main()

{

	int n, W;

	cin >> n >> W;



	vector<int> w(n + 1), v(n + 1);



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

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



	int V = *max_element(v.begin(), v.end()) * n;

	vector<vector<int>> dp(n + 1, vector<int>(V + 1, W + 1));





	dp[0][0] = 0;



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

	{

		for(int j = 0; j <= V; 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 = V; i > -1; i--)

	{

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

		{

			cout << i << endl;

			return 0;

		}

	}

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

using namespace std;

const int inf = 2e9+7;



long long w[101], v[101];

long long f[110][100100];



int main()

{

    int N, V, i, j;



    cin>>N>>V;



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

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

    fill(f[0],f[0]+100001,inf);

    f[0][0] = 0;

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

    {

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

            if(j >= v[i])

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

            else

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

    }

    int res=0;

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

        if(f[N][i]<=V)

            res = i;



    cout<<res<<endl;



    return 0;

}

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



using namespace std;





int main()

{

	int n, W;

	cin >> n >> W;



	vector<int> w(n + 1), v(n + 1);



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

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



	int V = *max_element(v.begin(), v.end()) * n;

	vector<vector<int>> dp(n + 1, vector<int>(V + 1, W + 1));





	dp[0][0] = 0;



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

	{

		for(int j = 0; j <= V; 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 = V; i > -1; i--)

	{

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

		{

			cout << i << endl;

			return 0;

		}

	}

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

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

ll n,W;

int w[100+10],v[100+10];

int dp[100+10][100000+10];

int main()

{

    cin>>n>>W;

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

    fill(dp[0],dp[0]+100000+1,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;

    return 0;

}

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

#include <limits.h>

#include <algorithm>  

#include <numeric>

 

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

using namespace std;

 

#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define endl '\n'

using ll = long long;

 

const int precision = 3;

const int modulo =  1000000007; // 10^9 + 7

const ll lmodulo =  1000000007; // 10^9 + 7

 

const double EPS = 1e-9;

const ll inf = 1e18;



void solve () {

	int n, W;  cin >> n >> W;

	vector<int> weight(n), value(n);

	

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

		cin >> weight[i] >> value[i];

	}



	int maxVal = accumulate(value.begin(), value.end(), 0);



	vector<vector<ll>> dp(weight.size() + 1, vector<ll>(maxVal + 1, inf));

	dp[0][0] = 0;



	for (auto i = 1; i < dp.size(); ++i) {

		const auto & w = weight[i - 1];

		const auto & cv = value[i - 1];

		for (int v = maxVal; v >= 0; --v) {

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

			if (v - cv >= 0) {

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

			}

		}

	}



	int ret = 0;

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

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

			ret = max(ret, i);

		}

	}

	cout << ret;

}



int main() {

  ios_base::sync_with_stdio(false);

  cin.tie(nullptr);

  cout.tie(nullptr);

  cout.precision(precision);

  cout.setf(ios_base::fixed);

  solve();

  return 0;

}