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



using namespace std;

typedef long long ll;



const int N = 107;

int w[N], v[N];

int n, W;



ll dp[2][100007];



ll infll;



int main() {

    memset(&infll, 0x3f, sizeof infll);

    cin >> n >> W;



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

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

    }



    int cur = 0;

    memset(dp, 0x3f, sizeof dp);

    dp[1-cur][0] = 0;

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

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

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

            if(j - v[i] >= 0 and dp[1-cur][j - v[i]] < infll) dp[cur][j] = min(dp[cur][j], w[i] + dp[1-cur][j - v[i]]);

        }

        cur = 1 - cur;

    }



    int ans = 0;

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

        if(dp[1-cur][j] <= W) ans = max(ans, j);

    }



    cout << ans << endl;

}

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

using namespace std;



typedef long long ll;

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

ll dp[102][100009],wt[102],v[102];



ll knapsack(ll n,ll s,ll w)

{

    ll a,b;

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

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

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

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

            else if(v[i]>j){

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

            }

            else

            {

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

                b= dp[i-1][j-v[i]]==-1? -1:wt[i]+dp[i-1][j-v[i]];

                if(a==-1 && b==-1)

                {

                    dp[i][j]=-1;

                }

                else if(a==-1)

                {

                    dp[i][j]=b;

                }

                else if(b==-1){

                    dp[i][j]=a;

                }

                else{

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

                }

            }

        }

        dp[0][0]=0;

    }

    

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

        if(dp[n][j]<=w && dp[n][j]!=-1) return j;

    }

}

int main()

{

   ll n,w,i,s=0;

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

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

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

        s+=v[i];

   }

 

   ll ans=knapsack(n,s,w);

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

   return 0;

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>

#include<iostream>

#include<algorithm>

#include<iomanip>

#include<string>

#include<cmath>

#include<vector>

#include<set>

#include<queue>

#include<stack>

#include<fstream>

#include<map>

#include<bitset>

#include<unordered_map>

#include<cstring>

#include<cctype>

using namespace std;

#define  ll long long

#define  ull unsigned long long

#define  ul unsigned long

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

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

#define pb(s) push_back(s);

#define format(n) fixed<<setprecision(n)

#define finl "\n"

#define Mohammed_Atef_Hassan fast();

#define mod 1000000007

#define INF LLONG_MAX

#define PI acos(-1)

#define clr(dp,n) memset(dp,n,sizeof dp)

#define ex(n) return cout<<n<<finl,0;

int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

int dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 };

ll fix_mod(ll x, ll y)

{

	return (y + x % y) % y;

}

void fast() {

	std::ios_base::sync_with_stdio(false);

	cin.tie(nullptr); cout.tie(nullptr);

}

int main()

{

	Mohammed_Atef_Hassan

		int n; ll w;

	cin >> n >> w;

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

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

	vector<ll>mem(1e5 + 10, LLONG_MAX);

	mem[0] = 0;

	set<int>st{ 0 };

	vector<int>vv;

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

	{

		vv.clear();

		for (set<int>::reverse_iterator j=st.rbegin();j!=st.rend();j++)

		{

			if (*j + v[i].second <= 1e5)

				mem[*j + v[i].second] = min(mem[*j + v[i].second], v[i].first+mem[*j]),vv.push_back(*j+v[i].second);

		}

		for (auto j : vv)st.insert(j);

	}

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

	{

		if(mem[i]<=w)ex(i);

	}

}

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

using namespace std;



typedef long long ll;

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

ll dp[102][100009],wt[102],v[102];



ll knapsack(ll n,ll s,ll w)

{

    ll a,b;

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

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

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

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

            else if(v[i]>j){

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

            }

            else

            {

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

                b= dp[i-1][j-v[i]]==-1? -1:wt[i]+dp[i-1][j-v[i]];

                if(a==-1 && b==-1)

                {

                    dp[i][j]=-1;

                }

                else if(a==-1)

                {

                    dp[i][j]=b;

                }

                else if(b==-1){

                    dp[i][j]=a;

                }

                else{

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

                }

            }

        }

        dp[0][0]=0;

    }

    

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

        if(dp[n][j]<=w && dp[n][j]!=-1) return j;

    }

}

int main()

{

   ll n,w,i,s=0;

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

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

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

        s+=v[i];

   }

 

   ll ans=knapsack(n,s,w);

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

   return 0;

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

using namespace std;



typedef long long ll;

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

ll dp[102][100009],wt[102],v[102];



ll knapsack(ll n,ll s,ll w)

{

    ll a,b;

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

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

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

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

            else if(v[i]>j){

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

            }

            else

            {

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

                b= dp[i-1][j-v[i]]==-1? -1:wt[i]+dp[i-1][j-v[i]];

                if(a==-1 && b==-1)

                {

                    dp[i][j]=-1;

                }

                else if(a==-1)

                {

                    dp[i][j]=b;

                }

                else if(b==-1){

                    dp[i][j]=a;

                }

                else{

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

                }

            }

        }

        dp[0][0]=0;

    }

    

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

        if(dp[n][j]<=w && dp[n][j]!=-1) return j;

    }

}

int main()

{

   ll n,w,i,s=0;

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

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

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

        s+=v[i];

   }

 

   ll ans=knapsack(n,s,w);

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

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

using namespace std;



typedef long long ll;

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

ll dp[102][100009],wt[102],v[102];



ll knapsack(ll n,ll s,ll w)

{

    ll a,b;

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

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

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

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

            else if(v[i]>j){

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

            }

            else

            {

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

                b= dp[i-1][j-v[i]]==-1? -1:wt[i]+dp[i-1][j-v[i]];

                if(a==-1 && b==-1)

                {

                    dp[i][j]=-1;

                }

                else if(a==-1)

                {

                    dp[i][j]=b;

                }

                else if(b==-1){

                    dp[i][j]=a;

                }

                else{

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

                }

            }

        }

        dp[0][0]=0;

    }

    

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

        if(dp[n][j]<=w && dp[n][j]!=-1) return j;

    }

}

int main()

{

   ll n,w,i,s=0;

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

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

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

        s+=v[i];

   }

 

   ll ans=knapsack(n,s,w);

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

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

using namespace std;



typedef long long ll;

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

ll dp[102][100009],wt[102],v[102];



ll knapsack(ll n,ll s,ll w)

{

    ll a,b;

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

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

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

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

            else if(v[i]>j){

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

            }

            else

            {

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

                b= dp[i-1][j-v[i]]==-1? -1:wt[i]+dp[i-1][j-v[i]];

                if(a==-1 && b==-1)

                {

                    dp[i][j]=-1;

                }

                else if(a==-1)

                {

                    dp[i][j]=b;

                }

                else if(b==-1){

                    dp[i][j]=a;

                }

                else{

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

                }

            }

        }

        dp[0][0]=0;

    }

    

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

        if(dp[n][j]<=w && dp[n][j]!=-1) return j;

    }

}

int main()

{

   ll n,w,i,s=0;

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

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

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

        s+=v[i];

   }

 

   ll ans=knapsack(n,s,w);

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

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

using namespace std;



typedef long long ll;

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

ll dp[102][100009],wt[102],v[102];



ll knapsack(ll n,ll s,ll w)

{

    ll a,b;

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

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

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

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

            else if(v[i]>j){

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

            }

            else

            {

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

                b= dp[i-1][j-v[i]]==-1? -1:wt[i]+dp[i-1][j-v[i]];

                if(a==-1 && b==-1)

                {

                    dp[i][j]=-1;

                }

                else if(a==-1)

                {

                    dp[i][j]=b;

                }

                else if(b==-1){

                    dp[i][j]=a;

                }

                else{

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

                }

            }

        }

        dp[0][0]=0;

    }

    

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

        if(dp[n][j]<=w && dp[n][j]!=-1) return j;

    }

}

int main()

{

   ll n,w,i,s=0;

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

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

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

        s+=v[i];

   }

 

   ll ans=knapsack(n,s,w);

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

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

using namespace std;



typedef long long ll;

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

ll dp[102][100009],wt[102],v[102];



ll knapsack(ll n,ll s,ll w)

{

    ll a,b;

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

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

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

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

            else if(v[i]>j){

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

            }

            else

            {

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

                b= dp[i-1][j-v[i]]==-1? -1:wt[i]+dp[i-1][j-v[i]];

                if(a==-1 && b==-1)

                {

                    dp[i][j]=-1;

                }

                else if(a==-1)

                {

                    dp[i][j]=b;

                }

                else if(b==-1){

                    dp[i][j]=a;

                }

                else{

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

                }

            }

        }

        dp[0][0]=0;

    }

    

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

        if(dp[n][j]<=w && dp[n][j]!=-1) return j;

    }

}

int main()

{

   ll n,w,i,s=0;

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

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

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

        s+=v[i];

   }

 

   ll ans=knapsack(n,s,w);

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

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

using namespace std;



typedef long long ll;

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

ll dp[102][100009],wt[102],v[102];



ll knapsack(ll n,ll s,ll w)

{

    ll a,b;

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

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

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

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

            else if(v[i]>j){

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

            }

            else

            {

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

                b= dp[i-1][j-v[i]]==-1? -1:wt[i]+dp[i-1][j-v[i]];

                if(a==-1 && b==-1)

                {

                    dp[i][j]=-1;

                }

                else if(a==-1)

                {

                    dp[i][j]=b;

                }

                else if(b==-1){

                    dp[i][j]=a;

                }

                else{

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

                }

            }

        }

        dp[0][0]=0;

    }

    

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

        if(dp[n][j]<=w && dp[n][j]!=-1) return j;

    }

}

int main()

{

   ll n,w,i,s=0;

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

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

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

        s+=v[i];

   }

 

   ll ans=knapsack(n,s,w);

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

   return 0;

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

using namespace std;

int f[105][100005];

int N,W;

int w[105],v[105];

int main()

{

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

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

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

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

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

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

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

	{

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

	    {

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

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

 	    }

	}

	int ans=0;

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

	   if(f[N][i] <= W) ans=i;//cout<<f[N][i]<<endl;

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

	return 0;

}

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

using namespace std;



typedef long long ll;

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

ll dp[102][100009],wt[102],v[102];



ll knapsack(ll n,ll s,ll w)

{

    ll a,b;

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

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

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

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

            else if(v[i]>j){

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

            }

            else

            {

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

                b= dp[i-1][j-v[i]]==-1? -1:wt[i]+dp[i-1][j-v[i]];

                if(a==-1 && b==-1)

                {

                    dp[i][j]=-1;

                }

                else if(a==-1)

                {

                    dp[i][j]=b;

                }

                else if(b==-1){

                    dp[i][j]=a;

                }

                else{

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

                }

            }

        }

        dp[0][0]=0;

    }

    

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

        if(dp[n][j]<=w && dp[n][j]!=-1) return j;

    }

}

int main()

{

   ll n,w,i,s=0;

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

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

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

        s+=v[i];

   }

 

   ll ans=knapsack(n,s,w);

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

   return 0;

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

#define f first

#define s second

#define pb push_back

#define ENDL '\n'

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

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

#define deb(a) cout << #a << ": " << a << ENDL

#define fore(i, a, b) for(int i(a), ThkMk(b); i < ThkMk; ++i)

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



using namespace std;



typedef long long lli;

typedef long double ld;

typedef pair<lli, lli> ii;

typedef vector<lli> vi;



int main()

{   _

    lli n, w, u, v; cin >> n >> w;

    lli MXV = 1e5 + 5;

    lli INF = 1e18;

    vector<lli> dp(MXV, INF);

    dp[0] = 0;

    fore(t, 0, n) {

        cin >> u >> v;

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

            if(dp[i] != INF) dp[i + v] = min(dp[i + v], dp[i] + u);

        }

    }

    lli ans = 0;

    fore(i, 1, MXV) if(dp[i] <= w) ans = i;

    cout << ans << ENDL;

    return 0;

}


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

using namespace std;



typedef long long ll;

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

ll dp[102][100009],wt[102],v[102];



ll knapsack(ll n,ll s,ll w)

{

    ll a,b;

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

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

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

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

            else if(v[i]>j){

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

            }

            else

            {

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

                b= dp[i-1][j-v[i]]==-1? -1:wt[i]+dp[i-1][j-v[i]];

                if(a==-1 && b==-1)

                {

                    dp[i][j]=-1;

                }

                else if(a==-1)

                {

                    dp[i][j]=b;

                }

                else if(b==-1){

                    dp[i][j]=a;

                }

                else{

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

                }

            }

        }

        dp[0][0]=0;

    }

    

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

        if(dp[n][j]<=w && dp[n][j]!=-1) return j;

    }

}

int main()

{

   ll n,w,i,s=0;

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

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

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

        s+=v[i];

   }

 

   ll ans=knapsack(n,s,w);

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

   return 0;

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

#include <set>

#include <cmath>

#include <queue>

#include <stack>

#include <vector>

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

//全华班

using namespace std;



#define fi first

#define se second

#define mp make_pair

#define LL long long

#define pll pair<LL, LL>

#define pii pair<int, int>



const LL mod = 1e9 + 7;

const int maxn = 1e5 + 5;

const LL inf = 0x3f3f3f3f;

const double eps = 1e-8;

const double pi = acos(-1.0);



int w[maxn], v[maxn], dp[maxn];



int main() {

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

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

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

	}

	memset(dp, 0x3f, sizeof dp);

	dp[0] = 0;

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

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

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

		}

	}

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

		if(dp[i] > W) continue;

		cout << i << endl; break;

	}

	return 0;

}

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

using namespace std;



typedef long long ll;

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

ll dp[102][100009],wt[102],v[102];



ll knapsack(ll n,ll s,ll w)

{

    ll a,b;

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

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

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

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

            else if(v[i]>j){

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

            }

            else

            {

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

                b= dp[i-1][j-v[i]]==-1? -1:wt[i]+dp[i-1][j-v[i]];

                if(a==-1 && b==-1)

                {

                    dp[i][j]=-1;

                }

                else if(a==-1)

                {

                    dp[i][j]=b;

                }

                else if(b==-1){

                    dp[i][j]=a;

                }

                else{

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

                }

            }

        }

        dp[0][0]=0;

    }

    

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

        if(dp[n][j]<=w && dp[n][j]!=-1) return j;

    }

}

int main()

{

   ll n,w,i,s=0;

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

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

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

        s+=v[i];

   }

 

   ll ans=knapsack(n,s,w);

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

   return 0;

}