stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#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;



}

 

// Optimized solution to the same problem (faster):
#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;



}

 

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

*/

// Optimized solution to the same problem (faster):
#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;

}

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

}

// Optimized solution to the same problem (faster):
// 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;

}

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

    }

}


// Optimized solution to the same problem (faster):
#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);

        }

}


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

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;

}

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

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

ll dp[100005];

int main(){

	int n,W;

	int w[105],v[105];

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

	int sum = 0;

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

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

		sum += v[i];

	}

	for(int i = 1;i <= sum;i++) dp[i] = 0x3f3f3f3f;

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

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

		//	dp[j] = 0x3f3f3f3f;

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

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

		}

	}

	/*这道题为啥从1开始：

	因为如果dp[0] = 0x3f3f3f3f;

	dp[j] = min(0x3f3f3f3f,0x3f3f3f3f + w[i])

	就不用解释了

	只要dp[0] = 0;

	那么dp[v[i]] = min(0x3f3f3f3f,0 + w[i]);



	极大注意：尽量在循环外面进行初始化

	*/

	ll ans = 0;

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

		if(dp[i] <= W){

			ans = i;

			break;

		}

	}

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

	return 0;

}

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

}

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

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

ll dp[100005];

int main(){

	int n,W;

	int w[105],v[105];

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

	int sum = 0;

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

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

		sum += v[i];

	}

	for(int i = 1;i <= sum;i++) dp[i] = 0x3f3f3f3f;

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

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

		//	dp[j] = 0x3f3f3f3f;

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

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

		}

	}

	/*这道题为啥从1开始：

	因为如果dp[0] = 0x3f3f3f3f;

	dp[j] = min(0x3f3f3f3f,0x3f3f3f3f + w[i])

	就不用解释了

	只要dp[0] = 0;

	那么dp[v[i]] = min(0x3f3f3f3f,0 + w[i]);



	极大注意：尽量在循环外面进行初始化

	*/

	ll ans = 0;

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

		if(dp[i] <= W){

			ans = i;

			break;

		}

	}

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

	return 0;

}

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

}

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

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

ll dp[100005];

int main(){

	int n,W;

	int w[105],v[105];

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

	int sum = 0;

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

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

		sum += v[i];

	}

	for(int i = 1;i <= sum;i++) dp[i] = 0x3f3f3f3f;

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

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

		//	dp[j] = 0x3f3f3f3f;

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

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

		}

	}

	/*这道题为啥从1开始：

	因为如果dp[0] = 0x3f3f3f3f;

	dp[j] = min(0x3f3f3f3f,0x3f3f3f3f + w[i])

	就不用解释了

	只要dp[0] = 0;

	那么dp[v[i]] = min(0x3f3f3f3f,0 + w[i]);



	极大注意：尽量在循环外面进行初始化

	*/

	ll ans = 0;

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

		if(dp[i] <= W){

			ans = i;

			break;

		}

	}

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

	return 0;

}

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




#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<string>

#include<cmath>

#include<map>

#include<bitset>

#include<utility>

//#include<unordered_map>

#ifdef LOCAL

#include"file.h"

#endif



using namespace std;



typedef long long LL;

typedef unsigned long long ULL;

const double eps = 1e-12;

const double Pi = 3.1415926535897932;

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

//const int dir[8][2] = { -2,-1,-2,1,2,-1,2,1,-1,2,-1,-2,1,2,1,-2 };



















































const int maxn = 1e5 + 5;

LL f[maxn];





int main() {

#ifdef LOCAL

	fileopen();

#endif

	int n, C;

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

	memset(f, 63, sizeof(f));

	f[0] = 0;

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

		int w, v;

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

		for (int i = maxn - 3; i >= v; i--)if (f[i - v] + w <= C) {

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

		}

	}

	LL ans = 0;

	for (int i = 0; i <= maxn - 3; i++)if (f[i] <= C)ans = max(ans, (LL)i);

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



#ifdef LOCAL

	fileclose();

#endif

	return 0;

}


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

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

ll dp[100005];

int main(){

	int n,W;

	int w[105],v[105];

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

	int sum = 0;

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

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

		sum += v[i];

	}

	for(int i = 1;i <= sum;i++) dp[i] = 0x3f3f3f3f;

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

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

		//	dp[j] = 0x3f3f3f3f;

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

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

		}

	}

	/*这道题为啥从1开始：

	因为如果dp[0] = 0x3f3f3f3f;

	dp[j] = min(0x3f3f3f3f,0x3f3f3f3f + w[i])

	就不用解释了

	只要dp[0] = 0;

	那么dp[v[i]] = min(0x3f3f3f3f,0 + w[i]);



	极大注意：尽量在循环外面进行初始化

	*/

	ll ans = 0;

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

		if(dp[i] <= W){

			ans = i;

			break;

		}

	}

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

	return 0;

}

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

#define ll long long

#define pb push_back

#define mod 1000000007

#define mp make_pair

#define pi acos(-1)

#define line cout<<"------------------"<<endl

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

#define filein freopen("input.txt","r",stdin)

#define fileout freopen("output.txt","w",stdout)

#define inf (int)1e9+7

using namespace std;

ll n ;

ll w[109],val[109];

ll dp[100009];

ll weight;

int  main()

{

    cin>>n>>weight;

    for(ll i=1;i<=100007;i++) dp[i]=inf;

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

    {

        cin>>w[i]>>val[i];

        for(ll j=100005;j>=val[i];j--)

        {

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

        }

    }

    for( ll i=100005;i>=0;i--)

    {

        if(dp[i]<=weight)

        {

            cout<<i<<endl;

            return 0;

        }

    }







}


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

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

ll dp[100005];

int main(){

	int n,W;

	int w[105],v[105];

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

	int sum = 0;

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

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

		sum += v[i];

	}

	for(int i = 1;i <= sum;i++) dp[i] = 0x3f3f3f3f;

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

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

		//	dp[j] = 0x3f3f3f3f;

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

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

		}

	}

	/*这道题为啥从1开始：

	因为如果dp[0] = 0x3f3f3f3f;

	dp[j] = min(0x3f3f3f3f,0x3f3f3f3f + w[i])

	就不用解释了

	只要dp[0] = 0;

	那么dp[v[i]] = min(0x3f3f3f3f,0 + w[i]);



	极大注意：尽量在循环外面进行初始化

	*/

	ll ans = 0;

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

		if(dp[i] <= W){

			ans = i;

			break;

		}

	}

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

	return 0;

}

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

#include <vector>

#define ll long long int



using namespace std;



struct Item {

	ll weight;

	ll value;

};



const ll INF = 1LL << 32;

vector<ll> dp(100001, INF);



ll knapSack(ll W, Item items[], ll n){

	ll sum = dp[0] = 0;

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

		sum += items[i].value;

    	for(ll j = sum; j >= items[i].value; j--){

         	dp[j] = min(dp[j], dp[j - items[i].value] + items[i].weight);

    	}

	}

	

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

		if(dp[i] <= W){

			return i;

		}

	}

}



int main(){

	Item items[100];

	ll N, W;

	cin >> N >> W;

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

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

	cout << knapSack(W, items, N) << endl;

	return 0;

}

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

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

ll dp[100005];

int main(){

	int n,W;

	int w[105],v[105];

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

	int sum = 0;

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

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

		sum += v[i];

	}

	for(int i = 1;i <= sum;i++) dp[i] = 0x3f3f3f3f;

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

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

		//	dp[j] = 0x3f3f3f3f;

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

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

		}

	}

	/*这道题为啥从1开始：

	因为如果dp[0] = 0x3f3f3f3f;

	dp[j] = min(0x3f3f3f3f,0x3f3f3f3f + w[i])

	就不用解释了

	只要dp[0] = 0;

	那么dp[v[i]] = min(0x3f3f3f3f,0 + w[i]);



	极大注意：尽量在循环外面进行初始化

	*/

	ll ans = 0;

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

		if(dp[i] <= W){

			ans = i;

			break;

		}

	}

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

	return 0;

}

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



using namespace std;

 

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

 

#define nl '\n'

 

#define y1 aza_ibagaliev

 

#define f first

#define s second

	

#define ed end()

#define bg begin()

#define rbg rbegin()

 

#define rv reverse

#define mp make_pair

#define pb push_back

#define ppb pop_back

#define ppf pop_front

 

#define sz size()

#define all(x) x.bg, x.ed

 

#define pll pair < ll, ll >

#define pii pair < int, int >

 

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

#define sqrd(x) ((x) * 1.0 * (x))

 

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

 

#define rnl cout << "----------------------------------------" << nl

 

#define bit __builtin_popcount

 

inline ll bip(ll x, ll n, ll mod){ll res=1;while(n){if(n & 1){res=(res*x)%mod;}x=(x*x)%mod;n>>=1;}return res;}

        	

const int ppr = 257;

const ll INF = 2e18;

const int inf = 2e9;

const int mod = 1e9 + 7;

const int N = 1e5 + 123;

const ld pi = 3.1741592653589793238462643;

 

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

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



int n, W, w[N], v[N];

ll dp[N];



main() {             	

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

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



//	srand(time(NULL));



	cin >> n >> W;



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

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



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

		dp[i] = INF;

                       

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

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

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

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

			}



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

		if(dp[i] <= W) return cout << i, 0;



    return 0;                                        

}

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

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

ll dp[100005];

int main(){

	int n,W;

	int w[105],v[105];

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

	int sum = 0;

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

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

		sum += v[i];

	}

	for(int i = 1;i <= sum;i++) dp[i] = 0x3f3f3f3f;

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

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

		//	dp[j] = 0x3f3f3f3f;

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

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

		}

	}

	/*这道题为啥从1开始：

	因为如果dp[0] = 0x3f3f3f3f;

	dp[j] = min(0x3f3f3f3f,0x3f3f3f3f + w[i])

	就不用解释了

	只要dp[0] = 0;

	那么dp[v[i]] = min(0x3f3f3f3f,0 + w[i]);



	极大注意：尽量在循环外面进行初始化

	*/

	ll ans = 0;

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

		if(dp[i] <= W){

			ans = i;

			break;

		}

	}

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

	return 0;

}

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

#define ll long long

#define ull unsigned long long

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

#define endl '\n'

#define main() int main()

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

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

#define pi acos(-1.0)

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

#define lowbit(x) ((x)&(-(x)))

#define pb push_back

#define binarycount __builtin_popcount(x)

#define tr t[root]

#define lson t[root << 1]

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

#define fir first

#define sec second

#define debug(x) cout<<x<<'\n'

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

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

#define pa(a) printf("%d",a)

#define pab(a,b) printf("%d%d",a,b)

#define pii pair<string,int>

using namespace std;



#define maxn 1000010

const int inf = 0x3f3f3f3f;

const int mod = 9973;

const double eps = 1e-8;

ll gcd(ll a, ll b) {return b==0?a:gcd(b, a%b);}

ll lcm(ll a, ll b) {return a/gcd(a, b)*b;}

int max(int x,int y){if(x>y) return x;return y;}

ll powmod(ll a,ll b){

    ull ans = 1, pow = a%mod;

    while(b) { if(b&1) ans = (ans*pow)%mod; pow = (pow*pow)%mod; b >>= 1; }

    return ans%mod;

}

ll v[105],w[105];	

ll dp[maxn],n,W,ans;

main()

{

	IO;

	cin>>n>>W;

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

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

	}

	ans=0;

	ms(dp,0x3f);

	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]<=W) ans=max(ans,(ll)j);

		}

	}

	cout<<ans<<endl;

} 

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

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

ll dp[100005];

int main(){

	int n,W;

	int w[105],v[105];

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

	int sum = 0;

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

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

		sum += v[i];

	}

	for(int i = 1;i <= sum;i++) dp[i] = 0x3f3f3f3f;

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

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

		//	dp[j] = 0x3f3f3f3f;

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

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

		}

	}

	/*这道题为啥从1开始：

	因为如果dp[0] = 0x3f3f3f3f;

	dp[j] = min(0x3f3f3f3f,0x3f3f3f3f + w[i])

	就不用解释了

	只要dp[0] = 0;

	那么dp[v[i]] = min(0x3f3f3f3f,0 + w[i]);



	极大注意：尽量在循环外面进行初始化

	*/

	ll ans = 0;

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

		if(dp[i] <= W){

			ans = i;

			break;

		}

	}

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

	return 0;

}

// Fastest known solution for this problem: