Problem: You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.

You want to find a subset of items to put such that:

* The total value of the items is as large as possible.
* The items have combined weight at most W, that is capacity of the knapsack.



Find the maximum total value of items in the knapsack.

Constraints

* 1 ≤ N ≤ 100
* 1 ≤ vi ≤ 100
* 1 ≤ wi ≤ 10,000,000
* 1 ≤ W ≤ 1,000,000,000

Input


N W
v1 w1
v2 w2
:
vN wN


The first line consists of the integers N and W. In the following N lines, the value and weight of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Examples

Input

4 5
4 2
5 2
2 1
8 3


Output

13


Input

2 20
5 9
4 10


Output

9

Solution (in CPP):

Solution:
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<map>
#include<algorithm>
#include<set>
#include <stdexcept>
#include<queue>
#include<stdio.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9+10;
typedef long long ll;
typedef pair<ll,int> P;
int ceil(int a,int b){// a以上bの倍数の最小値//
     return (a+b-1)/b*b;
 }
int stoii(string s){//stoi関数の代用 文字列⇒int型//
    return atoi(s.c_str());
}

char maze[51][51];
int n,m;
int sx,sy,gx,gy;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
void Hanoi(int n,const char* from,const char* work,const char* dest){
	if(n>=2) Hanoi(n-1,from,dest,work);
	cout<<n<<"->"<<"from"<<from<<"to"<<dest<<endl;

  if(n>=2) Hanoi(n-1,work,from,dest);
}
long long fibloop(int n){
	int f0=1,f1=1;
	if(n==0) return f0;
    else if(n==1) return f1;
	else{
		for(int j=1;j<n;j++){
			int copy=f1;
			f1=f0+f1;
			f0=copy;
		}
		return f1;
	}
}
int dp[101][10001];
int main(){
	int n,W;
	cin>>n>>W;
	vector<int> w(n,0);
	vector<int> v(n,0);
	rep(i,n){
		cin>>v[i]>>w[i];
	}
	for(int j=1;j<=10001;j++) dp[0][j]=inf;
	dp[0][0]=0;
	for(int i=1;i<n+1;i++){
		for(int j=0;j<=10000;j++){
			if(v[i-1]<=j) dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);
			else dp[i][j]=dp[i-1][j];
		}
	}
	int res=0;
	for(int j=0;j<=10000;j++){
		if(dp[n][j]<=W){
            res=j;
        } 
	}
	cout<<res<<endl; 
	return 0;
}