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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;


class Main{
	//今回は、価値は低くて、重さが大きいもののナップサック。
	//いままでは、価値をテーブルに格納していたが、今回は、同じ価値をできるだけ少ない重さで実現しようという計画。
	//その為、dpにminを使う
	public static void main(String[] args){
		SC sc=new SC(System.in);
		int N=sc.nextInt();
		int W=sc.nextInt();
		int[][] dp=new int[N+1][N*100+1];	//品物の番号、価値
		int INF=2000000014;
		for(int i=0; i<=N; i++){
			for(int j=0; j<=N*100; j++){
				dp[i][j]=INF;
			}
		}
		dp[0][0]=0;
		int[][] products=new int[N][2];
		for(int i=0; i<N; i++){
			products[i][0]=sc.nextInt();		//価値
			products[i][1]=sc.nextInt();		//重さ
		}

		for(int i=0; i<N; i++){
			for(int j=0; j<=N*100; j++){
				if(j-products[i][0]<0){
					dp[i+1][j]=dp[i][j];		//品物が買えないとき
				}
				else if(j-products[i][0]>=0 && dp[i][j-products[i][0]]+products[i][1]<=W){
					dp[i+1][j]=Math.min(dp[i][j], dp[i][j-products[i][0]]+products[i][1]);
				}
				else{
					dp[i+1][j]=dp[i][j];
				}
			}
		}
		int valmax=0;
		for(int i=0; i<=N*100; i++){
			if(dp[N][i]<=W){
				valmax=i;
			}
		}
		pl(valmax);
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void pl() {
		System.out.println();
	}
	public static void p(Object o) {
		System.out.print(o);
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
	}
}