stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
// @author: Amirul Islam



#include <bits/stdc++.h>

using namespace std;

#define LLI long long int

#define PII pair <int, int>



const int mx = 1e5+5;

const LLI INF = 1e10;



LLI dp[mx], w, val, N, W;



LLI max(LLI a, LLI b) {

    return (a > b ? a : b);

}



LLI knapsack(int N, int W) {

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

    dp[0] = 0;

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

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

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

            if (j >= val) dp[j] = min(dp[j], dp[j-val] + w);

        }

    }

    LLI ret = 0;

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

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

    }

    return ret;

} 



int main() {

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

    printf("%lld\n", knapsack(N, W));

    return 0;

}

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

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n;

ll **dp, w;

pair<ll, int> *x;

ll nap(int i, int rem)

{

    if(i == n && rem)

        return (ll)1e9 + 1;

    else if(!rem)

        return 0;

    if(~dp[i][rem])

        return dp[i][rem];

    ll first = nap(i + 1, rem), second = (ll)1e9 + 1;

    if(rem >= x[i].second)

        second = x[i].first + nap(i + 1, rem - x[i].second);

    return dp[i][rem] = min(first, second);

}

int main()

{

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

    #ifndef ONLINE_JUDGE

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

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

    #endif

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

    x = new pair<ll, int>[n];

    int mx = 0;

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

    {

        scanf("%lld %d", &x[i].first, &x[i].second);

        mx += x[i].second;

    }

    dp = new ll*[n];

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

    {

        dp[i] = new ll[mx + 1];

        memset(dp[i], -1, (mx + 1) * 8);

    }

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

        if(nap(0, i) <= w)

        {

            printf("%d", i);

            break;

        }

}


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

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const int N=1005;

const int maxn=1e5+5;

ll a[N],v[N];

ll dp[maxn];

int main(){

	int n,k;

	cin>>n>>k;

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

		cin>>a[i]>>v[i];

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

	dp[0]=0;

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

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

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

	ll ans=0;

	for(int i=1;i<=maxn-5;++i)

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

	cout<<ans<<endl;

	return 0;

} 

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

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n;

ll **dp, w;

pair<ll, int> *x;

ll nap(int i, int rem)

{

    if(i == n && rem)

        return (ll)1e9 + 1;

    else if(!rem)

        return 0;

    if(~dp[i][rem])

        return dp[i][rem];

    ll first = nap(i + 1, rem), second = (ll)1e9 + 1;

    if(rem >= x[i].second)

        second = x[i].first + nap(i + 1, rem - x[i].second);

    return dp[i][rem] = min(first, second);

}

int main()

{

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

    #ifndef ONLINE_JUDGE

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

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

    #endif

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

    x = new pair<ll, int>[n];

    int mx = 0;

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

    {

        scanf("%lld %d", &x[i].first, &x[i].second);

        mx += x[i].second;

    }

    dp = new ll*[n];

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

    {

        dp[i] = new ll[mx + 1];

        memset(dp[i], -1, (mx + 1) * 8);

    }

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

        if(nap(0, i) <= w)

        {

            printf("%d", i);

            break;

        }

}


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

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <iomanip>

#include <string>

#include <set>

#include <vector>

#include <queue>

#include <stack>

using namespace std;

#define ms(a, x) memset(a, x, sizeof(a))

#define fore(i, a, n) for (long long i = a; i < n; i++)

#define ford(i, a, n) for (long long i = n - 1; i >= a; i--)

#define si(a) scanf("%d", &a)

#define sii(a, b) scanf("%d%d", &a, &b)

#define debug(a) cout << a << endl

#define endl '\n'

#define pi acos(-1.0)

#define tr t[root]

#define lson t[root << 1]

#define rson t[root << 1 | 1]

#define IO ios::sync_with_stdio(false), cin.tie(0)

const double eps = 1e-8;

inline int sgn(const double &x) { return x < -eps ? -1 : x > eps; }

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int maxn=1000100;

#define maxn0 1e9+7;

//=================================================



ll sum;

ll w[maxn];

ll dp[maxn];

ll v[maxn];



// void init() {

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

//         w[i]=0;

//         v[i]=0;

//     }

// }

int main() {

    IO;

    ll n,W;

    cin>>n>>W;

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

    dp[0]=0;

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

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

        // sum+=v[i];

    }

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

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

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

        }

    }

    ll ans=-1;

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

        if(dp[i]<=W)

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

    }

    cout<<ans<<endl;



    return 0;

}

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

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n;

ll **dp, w;

pair<ll, int> *x;

ll nap(int i, int rem)

{

    if(i == n && rem)

        return (ll)1e9 + 1;

    else if(!rem)

        return 0;

    if(~dp[i][rem])

        return dp[i][rem];

    ll first = nap(i + 1, rem), second = (ll)1e9 + 1;

    if(rem >= x[i].second)

        second = x[i].first + nap(i + 1, rem - x[i].second);

    return dp[i][rem] = min(first, second);

}

int main()

{

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

    #ifndef ONLINE_JUDGE

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

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

    #endif

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

    x = new pair<ll, int>[n];

    int mx = 0;

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

    {

        scanf("%lld %d", &x[i].first, &x[i].second);

        mx += x[i].second;

    }

    dp = new ll*[n];

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

    {

        dp[i] = new ll[mx + 1];

        memset(dp[i], -1, (mx + 1) * 8);

    }

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

        if(nap(0, i) <= w)

        {

            printf("%d", i);

            break;

        }

}


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

using namespace std;

const int N = 1e5+100;

const int M = 200;

typedef long long ll;

int a[N],b[N],n,m;

ll f[N];



int main(){

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

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

		scanf("%d%d",&a[i],&b[i]);

	memset(f, 0x3f, sizeof f);

	f[0] = 0;

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

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

			if (j - b[i] >= 0) f[j] = min(f[j], f[j-b[i]] + a[i]);



	int ans = 0;

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

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

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

	return 0;

}

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

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n;

ll **dp, w;

pair<ll, int> *x;

ll nap(int i, int rem)

{

    if(i == n && rem)

        return (ll)1e9 + 1;

    else if(!rem)

        return 0;

    if(~dp[i][rem])

        return dp[i][rem];

    ll first = nap(i + 1, rem), second = (ll)1e9 + 1;

    if(rem >= x[i].second)

        second = x[i].first + nap(i + 1, rem - x[i].second);

    return dp[i][rem] = min(first, second);

}

int main()

{

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

    #ifndef ONLINE_JUDGE

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

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

    #endif

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

    x = new pair<ll, int>[n];

    int mx = 0;

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

    {

        scanf("%lld %d", &x[i].first, &x[i].second);

        mx += x[i].second;

    }

    dp = new ll*[n];

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

    {

        dp[i] = new ll[mx + 1];

        memset(dp[i], -1, (mx + 1) * 8);

    }

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

        if(nap(0, i) <= w)

        {

            printf("%d", i);

            break;

        }

}


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

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<stack>

#define LL long long

using namespace std;

LL n,m;

LL dp[100011];

LL x,y,ans;

LL read()

{

	LL _=0,__=1;char ch=getchar();

	while(ch<'0'||ch>'9') {if(ch=='-')__=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){_=_*10+ch-'0';ch=getchar();}

	return _*__;

}

int main()

{

	n=read();m=read(); 

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

	dp[i]=1e9+7;

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

	{

		x=read();y=read();

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

		{

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

		}

	}

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

	{

		if(dp[i]<=m)

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

	}

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

	return 0;

}


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

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n;

ll **dp, w;

pair<ll, int> *x;

ll nap(int i, int rem)

{

    if(i == n && rem)

        return (ll)1e9 + 1;

    else if(!rem)

        return 0;

    if(~dp[i][rem])

        return dp[i][rem];

    ll first = nap(i + 1, rem), second = (ll)1e9 + 1;

    if(rem >= x[i].second)

        second = x[i].first + nap(i + 1, rem - x[i].second);

    return dp[i][rem] = min(first, second);

}

int main()

{

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

    #ifndef ONLINE_JUDGE

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

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

    #endif

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

    x = new pair<ll, int>[n];

    int mx = 0;

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

    {

        scanf("%lld %d", &x[i].first, &x[i].second);

        mx += x[i].second;

    }

    dp = new ll*[n];

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

    {

        dp[i] = new ll[mx + 1];

        memset(dp[i], -1, (mx + 1) * 8);

    }

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

        if(nap(0, i) <= w)

        {

            printf("%d", i);

            break;

        }

}


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

#define MAX 100005

#define pb push_back

#define mp make_pair

#define pii pair<long long,long long>

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

#define p1(a) cout<<"Check "<<a<<endl;

#define p2(a,b) cout<<"Check "<<a<<' '<<b<<endl;

#define p3(a,b,c) cout<<"Check "<<a<<' '<<b<<' '<<c<<endl;

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

#define ll long long

#define clr(a) memset(a,0,sizeof(a))

#define MOD 10000000000

#define INF 10000000000000



using namespace std;



int n,cp;

ll cost[MAX];

ll weight[MAX];

ll dp[MAX];





int main()

{

    cin>>n>>cp;

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

        scanf("%lld%lld",&weight[i],&cost[i]);

    }

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

    dp[0]=0;

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

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

            if(j-cost[i]>=0 && dp[j-cost[i]]!=INF){

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

            }

        }

    }

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

        if(dp[j]<=cp){

            cout<<j<<endl;

            break;

            //break;

        }

    }



    return 0;

}


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

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n;

ll **dp, w;

pair<ll, int> *x;

ll nap(int i, int rem)

{

    if(i == n && rem)

        return (ll)1e9 + 1;

    else if(!rem)

        return 0;

    if(~dp[i][rem])

        return dp[i][rem];

    ll first = nap(i + 1, rem), second = (ll)1e9 + 1;

    if(rem >= x[i].second)

        second = x[i].first + nap(i + 1, rem - x[i].second);

    return dp[i][rem] = min(first, second);

}

int main()

{

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

    #ifndef ONLINE_JUDGE

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

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

    #endif

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

    x = new pair<ll, int>[n];

    int mx = 0;

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

    {

        scanf("%lld %d", &x[i].first, &x[i].second);

        mx += x[i].second;

    }

    dp = new ll*[n];

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

    {

        dp[i] = new ll[mx + 1];

        memset(dp[i], -1, (mx + 1) * 8);

    }

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

        if(nap(0, i) <= w)

        {

            printf("%d", i);

            break;

        }

}


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

#include <cstring>

using namespace std;

const int maxn=1e5+5;

using ll = long long;

ll dp[maxn];

ll w[maxn],v[maxn];

int main()

{

   ll n,m,mm;

   cin>>n>>mm;

   m=0;

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

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

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

       m+=v[i];

   }

   dp[0]=0;

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

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

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

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

       }

   }

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

       if(dp[i]<=mm){

           cout<<i<<endl;

           break;

       }

   }

   return 0;

}


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

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n;

ll **dp, w;

pair<ll, int> *x;

ll nap(int i, int rem)

{

    if(i == n && rem)

        return (ll)1e9 + 1;

    else if(!rem)

        return 0;

    if(~dp[i][rem])

        return dp[i][rem];

    ll first = nap(i + 1, rem), second = (ll)1e9 + 1;

    if(rem >= x[i].second)

        second = x[i].first + nap(i + 1, rem - x[i].second);

    return dp[i][rem] = min(first, second);

}

int main()

{

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

    #ifndef ONLINE_JUDGE

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

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

    #endif

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

    x = new pair<ll, int>[n];

    int mx = 0;

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

    {

        scanf("%lld %d", &x[i].first, &x[i].second);

        mx += x[i].second;

    }

    dp = new ll*[n];

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

    {

        dp[i] = new ll[mx + 1];

        memset(dp[i], -1, (mx + 1) * 8);

    }

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

        if(nap(0, i) <= w)

        {

            printf("%d", i);

            break;

        }

}


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



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

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

#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)

#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)

#define pb push_back

#define eb emplace_back

#define ms(a, x) memset(a, x, sizeof(a))

#define F first

#define S second

#define endl '\n'

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

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



using namespace std;



typedef long long ll;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());



const int N=1e5+5;

ll dp[N];

int v[105],w[105];

int main() {



    ios::sync_with_stdio(false);

    cin.tie(nullptr);

	int N,W;

	cin>>N>>W;

	int sum=0;

	forn(i,N){

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

		sum+=v[i];

	}

	ms(dp,INF);

	dp[0]=0;

	forn(i,N){

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

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

		}

	}

	ll ans=0;

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

		if(dp[i]<=W){

			ans=i;

			break;

		}

	}

	cout<<ans;

	return 0;

}




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

#include <unordered_map>

#include <unordered_set>

#define endl '\n'

#define PI acos(-1)

typedef long long ll;

using namespace std;

int n;

ll **dp, w;

pair<ll, int> *x;

ll nap(int i, int rem)

{

    if(i == n && rem)

        return (ll)1e9 + 1;

    else if(!rem)

        return 0;

    if(~dp[i][rem])

        return dp[i][rem];

    ll first = nap(i + 1, rem), second = (ll)1e9 + 1;

    if(rem >= x[i].second)

        second = x[i].first + nap(i + 1, rem - x[i].second);

    return dp[i][rem] = min(first, second);

}

int main()

{

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

    #ifndef ONLINE_JUDGE

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

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

    #endif

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

    x = new pair<ll, int>[n];

    int mx = 0;

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

    {

        scanf("%lld %d", &x[i].first, &x[i].second);

        mx += x[i].second;

    }

    dp = new ll*[n];

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

    {

        dp[i] = new ll[mx + 1];

        memset(dp[i], -1, (mx + 1) * 8);

    }

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

        if(nap(0, i) <= w)

        {

            printf("%d", i);

            break;

        }

}


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

#define ll long long

using namespace std;

#define inf 0x3f3f3f3f 

#define MAXN 1019191130

int main(){

	ll  n , W; cin >> n >> W;

    ll w[101] , v[101] , dp[100001];

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

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

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

        dp[0] = 0;

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

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

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

        }

    }

    int j = 100001;

    while(j-- && dp[j] > W);



    cout<< j <<endl;

}

// 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;

int main()

{

	 int n,W;

    cin>>n>>W;

    long long w[n];

    long long v[n];

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

    long long dp[100005];

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

    {

    	dp[i]=1e15;

	}

    dp[0]=0;

    int res=0;

    for(int i=0;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]<=W){

                res=max(res,j);

            }

        }

    }

    cout<<res<<endl;

}

// 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 <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN=1e5+7;

int N,W,ans;

ll w[MAXN],v[MAXN],f[MAXN];

int main()

{

	cin>>N>>W;

	for(int i=1;i<=N;i++) cin>>w[i]>>v[i];

	memset(f,127,sizeof(f));

	f[0]=0;

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

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

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

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

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

	cout<<ans<<endl;

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

#include <cassert>

#include <algorithm>

#define N int(1e5+1)

using namespace std;

typedef pair<int,int> pii;

int dp[N];

struct{

    int w,v;

}a[100];

int main(int argc,char ** argv)

{

    int n,w;

    cin>>n>>w;

    fill(dp+1,dp+N,w+1);

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

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

    }

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

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

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

        }

    }

    int i;

    for(i=N-1;dp[i]>w;--i);

    cout<<i<<endl;

    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: