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

using namespace std;

#define INF 10e10

#define LL long long int

LL dp[100001];

int main() {

    ios_base::sync_with_stdio(false);

    int n,w,valSum=0;

    cin >> n >> w;

    int wgt[n+1],val[n+1];

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

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

        cin >> wgt[i] >> val[i];

        valSum += val[i];

    }

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

        for(int j=valSum; j>=val[i]; j--) {

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

        }

    }

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

        if(dp[i]<=w) {

            cout << i << "\n";

            break;

        }

    }

}


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

using namespace std;

#define pb push_back

#define POP pop_back()

#define ll long long

#define db double

#define POP pop_back()

#define endl '\n'

const int maxn = 1e5 + 5;

const int inf = 0x3f3f3f3f;

const int mod = 1e9 + 7;

const ll inF = 0x3f3f3f3f3f3f3f3f;

struct node{

	int w , v;

};

node a[maxn];

ll dp[maxn];

int main(){

	int n , c;cin >> n >> c;

	int w , v , tmp = 0;

	for(int i = 1;i <= n;i++)cin >> a[i].w >> a[i].v , tmp+=a[i].v;

	for(int i = 1;i <= tmp;i++)dp[i] = inF;

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

		for(int j = tmp;j >= a[i].v;j--){

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

		}

	}

	int ans = 0;

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

		if(dp[i] <= c){

			ans = i;

			break;

		}

	}

	cout << ans << endl;

	return 0;

}
// Slower C++ solution:
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#include<bits/stdc++.h>  

#define endl "\n"

using namespace std;

	typedef long long ll;

	const int maxn=100050;

	const int inf=0x3f3f3f3f;

	ll w[105];

	ll v[105];

	ll dp[maxn];

	ll n,m;

	int main(){

		IOS

		cin>>n>>m;

		ll sum=0;

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

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

			sum+=v[i];

		}

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

		dp[0]=0;	

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

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

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

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

			

		ll ans=-1;

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

			if(dp[j]<=m){

				ans=j;

				break;

			}

		}

		cout<<ans<<endl;

	}

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

using namespace std;

#define pb push_back

#define POP pop_back()

#define ll long long

#define db double

#define POP pop_back()

#define endl '\n'

const int maxn = 1e5 + 5;

const int inf = 0x3f3f3f3f;

const int mod = 1e9 + 7;

const ll inF = 0x3f3f3f3f3f3f3f3f;

struct node{

	int w , v;

};

node a[maxn];

ll dp[maxn];

int main(){

	int n , c;cin >> n >> c;

	int w , v , tmp = 0;

	for(int i = 1;i <= n;i++)cin >> a[i].w >> a[i].v , tmp+=a[i].v;

	for(int i = 1;i <= tmp;i++)dp[i] = inF;

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

		for(int j = tmp;j >= a[i].v;j--){

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

		}

	}

	int ans = 0;

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

		if(dp[i] <= c){

			ans = i;

			break;

		}

	}

	cout << ans << endl;

	return 0;

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

#include<cstring>

using namespace std;

int main()

{

	long long n,V;

	long long w[105],v[105],dp[100025];

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

    cin>>n>>V;

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

    {

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

    }

    long long ans=0;

    dp[0]=0;

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

	{

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

        {

            {

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

                if(dp[j]<=V)

                    ans=max(ans,1ll*j);

            }

        }

    }

    cout<<ans<<endl;

    return 0;

}

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

using namespace std;

#define pb push_back

#define POP pop_back()

#define ll long long

#define db double

#define POP pop_back()

#define endl '\n'

const int maxn = 1e5 + 5;

const int inf = 0x3f3f3f3f;

const int mod = 1e9 + 7;

const ll inF = 0x3f3f3f3f3f3f3f3f;

struct node{

	int w , v;

};

node a[maxn];

ll dp[maxn];

int main(){

	int n , c;cin >> n >> c;

	int w , v , tmp = 0;

	for(int i = 1;i <= n;i++)cin >> a[i].w >> a[i].v , tmp+=a[i].v;

	for(int i = 1;i <= tmp;i++)dp[i] = inF;

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

		for(int j = tmp;j >= a[i].v;j--){

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

		}

	}

	int ans = 0;

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

		if(dp[i] <= c){

			ans = i;

			break;

		}

	}

	cout << ans << endl;

	return 0;

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

#include<cstring>

using namespace std;

const int maxn=1e5+10;

const int inf=0x3f3f3f;

int v[110];

long long w[110];

long long dp[maxn];

int main()

{

	int n,m;

	cin>>n>>m;

	int ans=0;

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

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

	memset(dp,inf,sizeof(dp));

	dp[0]=0;

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

	{

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

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

	}

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

	{

		if(dp[i]<=m)

		 ans=max(ans,i);

	}

	cout<<ans<<endl;

	return 0;

}

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

using namespace std;

#define pb push_back

#define POP pop_back()

#define ll long long

#define db double

#define POP pop_back()

#define endl '\n'

const int maxn = 1e5 + 5;

const int inf = 0x3f3f3f3f;

const int mod = 1e9 + 7;

const ll inF = 0x3f3f3f3f3f3f3f3f;

struct node{

	int w , v;

};

node a[maxn];

ll dp[maxn];

int main(){

	int n , c;cin >> n >> c;

	int w , v , tmp = 0;

	for(int i = 1;i <= n;i++)cin >> a[i].w >> a[i].v , tmp+=a[i].v;

	for(int i = 1;i <= tmp;i++)dp[i] = inF;

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

		for(int j = tmp;j >= a[i].v;j--){

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

		}

	}

	int ans = 0;

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

		if(dp[i] <= c){

			ans = i;

			break;

		}

	}

	cout << ans << endl;

	return 0;

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

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=100025;

const int inf=0x3f3f3f3f;

int n,m;

int w[maxn];

ll v[maxn];

ll val[maxn];

ll dp[maxn];

int main()

{

    int n,V;

	ll ans=0;

	cin>>n>>V;

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

    cin>>v[i]>>val[i];

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

    dp[0]=0;

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

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

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

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

	if(dp[i]<=V) 

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

	cout<<ans<<endl;

}


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

using namespace std;

#define pb push_back

#define POP pop_back()

#define ll long long

#define db double

#define POP pop_back()

#define endl '\n'

const int maxn = 1e5 + 5;

const int inf = 0x3f3f3f3f;

const int mod = 1e9 + 7;

const ll inF = 0x3f3f3f3f3f3f3f3f;

struct node{

	int w , v;

};

node a[maxn];

ll dp[maxn];

int main(){

	int n , c;cin >> n >> c;

	int w , v , tmp = 0;

	for(int i = 1;i <= n;i++)cin >> a[i].w >> a[i].v , tmp+=a[i].v;

	for(int i = 1;i <= tmp;i++)dp[i] = inF;

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

		for(int j = tmp;j >= a[i].v;j--){

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

		}

	}

	int ans = 0;

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

		if(dp[i] <= c){

			ans = i;

			break;

		}

	}

	cout << ans << endl;

	return 0;

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

}


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

using namespace std;

typedef long long int ll;



ll knapSack(ll n,ll v[],ll W,ll w[],ll tot)

{

    ll K[n+5][tot+5];

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

    {

        for (ll pr=0; pr<=tot; pr++)

        {

            if (i==0 && pr==0)

                K[i][pr]=0;

            else if(i==0)

                K[i][pr]=1e11;

            /*else if(w[i-1]<=wt)

                K[i][wt]=max(v[i-1]+K[i-1][wt-w[i-1]],K[i-1][wt]);*/

            else if(v[i-1]<=pr)

                K[i][pr]=min(w[i-1]+K[i-1][pr-v[i-1]],K[i-1][pr]);

            else

                K[i][pr]=K[i-1][pr];

        }

    }

    ll val=0;

	for(ll pr=0; pr<=tot; pr++)

		if(K[n][pr]<=W)

            val=pr;

	return val;

}



int main()

{

    ll n,W;

    cin>>n>>W;

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

    ll tot=0;

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

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

        tot+=v[i];

    }

    ll ans=knapSack(n,v,W,w,tot);

    cout<<ans<<endl;

    return 0;

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

}




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

using namespace std;

typedef long long int ll;



ll knapSack(ll n,ll v[],ll W,ll w[],ll tot)

{

    ll K[n+5][tot+5];

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

    {

        for (ll pr=0; pr<=tot; pr++)

        {

            if (i==0 && pr==0)

                K[i][pr]=0;

            else if(i==0)

                K[i][pr]=1e11;

            /*else if(w[i-1]<=wt)

                K[i][wt]=max(v[i-1]+K[i-1][wt-w[i-1]],K[i-1][wt]);*/

            else if(v[i-1]<=pr)

                K[i][pr]=min(w[i-1]+K[i-1][pr-v[i-1]],K[i-1][pr]);

            else

                K[i][pr]=K[i-1][pr];

        }

    }

    ll val=0;

	for(ll pr=0; pr<=tot; pr++)

		if(K[n][pr]<=W)

            val=pr;

	return val;

}



int main()

{

    ll n,W;

    cin>>n>>W;

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

    ll tot=0;

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

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

        tot+=v[i];

    }

    ll ans=knapSack(n,v,W,w,tot);

    cout<<ans<<endl;

    return 0;

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

}




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

using namespace std;

typedef long long int ll;



ll knapSack(ll n,ll v[],ll W,ll w[],ll tot)

{

    ll K[n+5][tot+5];

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

    {

        for (ll pr=0; pr<=tot; pr++)

        {

            if (i==0 && pr==0)

                K[i][pr]=0;

            else if(i==0)

                K[i][pr]=1e11;

            /*else if(w[i-1]<=wt)

                K[i][wt]=max(v[i-1]+K[i-1][wt-w[i-1]],K[i-1][wt]);*/

            else if(v[i-1]<=pr)

                K[i][pr]=min(w[i-1]+K[i-1][pr-v[i-1]],K[i-1][pr]);

            else

                K[i][pr]=K[i-1][pr];

        }

    }

    ll val=0;

	for(ll pr=0; pr<=tot; pr++)

		if(K[n][pr]<=W)

            val=pr;

	return val;

}



int main()

{

    ll n,W;

    cin>>n>>W;

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

    ll tot=0;

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

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

        tot+=v[i];

    }

    ll ans=knapSack(n,v,W,w,tot);

    cout<<ans<<endl;

    return 0;

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

}

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

using namespace std;

typedef long long int ll;



ll knapSack(ll n,ll v[],ll W,ll w[],ll tot)

{

    ll K[n+5][tot+5];

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

    {

        for (ll pr=0; pr<=tot; pr++)

        {

            if (i==0 && pr==0)

                K[i][pr]=0;

            else if(i==0)

                K[i][pr]=1e11;

            /*else if(w[i-1]<=wt)

                K[i][wt]=max(v[i-1]+K[i-1][wt-w[i-1]],K[i-1][wt]);*/

            else if(v[i-1]<=pr)

                K[i][pr]=min(w[i-1]+K[i-1][pr-v[i-1]],K[i-1][pr]);

            else

                K[i][pr]=K[i-1][pr];

        }

    }

    ll val=0;

	for(ll pr=0; pr<=tot; pr++)

		if(K[n][pr]<=W)

            val=pr;

	return val;

}



int main()

{

    ll n,W;

    cin>>n>>W;

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

    ll tot=0;

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

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

        tot+=v[i];

    }

    ll ans=knapSack(n,v,W,w,tot);

    cout<<ans<<endl;

    return 0;

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

}

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

using namespace std;

typedef long long int ll;



ll knapSack(ll n,ll v[],ll W,ll w[],ll tot)

{

    ll K[n+5][tot+5];

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

    {

        for (ll pr=0; pr<=tot; pr++)

        {

            if (i==0 && pr==0)

                K[i][pr]=0;

            else if(i==0)

                K[i][pr]=1e11;

            /*else if(w[i-1]<=wt)

                K[i][wt]=max(v[i-1]+K[i-1][wt-w[i-1]],K[i-1][wt]);*/

            else if(v[i-1]<=pr)

                K[i][pr]=min(w[i-1]+K[i-1][pr-v[i-1]],K[i-1][pr]);

            else

                K[i][pr]=K[i-1][pr];

        }

    }

    ll val=0;

	for(ll pr=0; pr<=tot; pr++)

		if(K[n][pr]<=W)

            val=pr;

	return val;

}



int main()

{

    ll n,W;

    cin>>n>>W;

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

    ll tot=0;

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

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

        tot+=v[i];

    }

    ll ans=knapSack(n,v,W,w,tot);

    cout<<ans<<endl;

    return 0;

}
// 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: 10.548041592349305x):
#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;



ll knapSack(ll n,ll v[],ll W,ll w[],ll tot)

{

    ll K[n+5][tot+5];

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

    {

        for (ll pr=0; pr<=tot; pr++)

        {

            if (i==0 && pr==0)

                K[i][pr]=0;

            else if(i==0)

                K[i][pr]=1e11;

            /*else if(w[i-1]<=wt)

                K[i][wt]=max(v[i-1]+K[i-1][wt-w[i-1]],K[i-1][wt]);*/

            else if(v[i-1]<=pr)

                K[i][pr]=min(w[i-1]+K[i-1][pr-v[i-1]],K[i-1][pr]);

            else

                K[i][pr]=K[i-1][pr];

        }

    }

    ll val=0;

	for(ll pr=0; pr<=tot; pr++)

		if(K[n][pr]<=W)

            val=pr;

	return val;

}



int main()

{

    ll n,W;

    cin>>n>>W;

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

    ll tot=0;

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

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

        tot+=v[i];

    }

    ll ans=knapSack(n,v,W,w,tot);

    cout<<ans<<endl;

    return 0;

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

using namespace std;

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

#define ll long long

#define fastIO cout << fixed << setprecision(9), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

double const EPS = 1e-9, PI = acos(-1);

const int N = 2e5 + 9, M = 5e2 + 9, OO = 1e9 + 7, MOD = 1e9 + 9;

const ll inf = 1e18;



ll dp[N], weight[109];

int val[109];



int main() {

  fastIO;

#ifdef LOCAL

  freopen("input.in", "rt", stdin);

#endif

  int n, k;

  cin >> n >> k;

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

    cin >> weight[i] >> val[i];

  memset(dp, '?', sizeof dp);

  int ans = 0;

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

    dp[0] = 0;

//    dp[i][val[i]] = min(dp[i][val[i]], weight[i]);

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

      ans = max(ans, val[i]);

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

      if(j + val[i] >= N) continue;

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

      if(dp[j + val[i]] <= k)

        ans = max(ans, j + val[i]);

    }

  }

  cout << ans;

  return 0;

}


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

using namespace std;

typedef long long int ll;



ll knapSack(ll n,ll v[],ll W,ll w[],ll tot)

{

    ll K[n+5][tot+5];

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

    {

        for (ll pr=0; pr<=tot; pr++)

        {

            if (i==0 && pr==0)

                K[i][pr]=0;

            else if(i==0)

                K[i][pr]=1e11;

            /*else if(w[i-1]<=wt)

                K[i][wt]=max(v[i-1]+K[i-1][wt-w[i-1]],K[i-1][wt]);*/

            else if(v[i-1]<=pr)

                K[i][pr]=min(w[i-1]+K[i-1][pr-v[i-1]],K[i-1][pr]);

            else

                K[i][pr]=K[i-1][pr];

        }

    }

    ll val=0;

	for(ll pr=0; pr<=tot; pr++)

		if(K[n][pr]<=W)

            val=pr;

	return val;

}



int main()

{

    ll n,W;

    cin>>n>>W;

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

    ll tot=0;

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

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

        tot+=v[i];

    }

    ll ans=knapSack(n,v,W,w,tot);

    cout<<ans<<endl;

    return 0;

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

#include<cmath>

#include<cstdio>

#include<cstring>

using namespace std;

long long n,m,f[100010],w[100200],v[100200];

int main ()

{

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

	f[0]=0;

	cin>>n>>m;

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

	{

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

	}

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

	{

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

		{

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

		}

	}	

	long long ans=0;

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

	{

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

	}

	cout<<ans;

}


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

using namespace std;

typedef long long int ll;



ll knapSack(ll n,ll v[],ll W,ll w[],ll tot)

{

    ll K[n+5][tot+5];

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

    {

        for (ll pr=0; pr<=tot; pr++)

        {

            if (i==0 && pr==0)

                K[i][pr]=0;

            else if(i==0)

                K[i][pr]=1e11;

            /*else if(w[i-1]<=wt)

                K[i][wt]=max(v[i-1]+K[i-1][wt-w[i-1]],K[i-1][wt]);*/

            else if(v[i-1]<=pr)

                K[i][pr]=min(w[i-1]+K[i-1][pr-v[i-1]],K[i-1][pr]);

            else

                K[i][pr]=K[i-1][pr];

        }

    }

    ll val=0;

	for(ll pr=0; pr<=tot; pr++)

		if(K[n][pr]<=W)

            val=pr;

	return val;

}



int main()

{

    ll n,W;

    cin>>n>>W;

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

    ll tot=0;

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

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

        tot+=v[i];

    }

    ll ans=knapSack(n,v,W,w,tot);

    cout<<ans<<endl;

    return 0;

}