Có ~N~ viên bi, được đánh số ~1,2,3,\ldots,N~. Với mỗi ~i~ ~(1 \le i \le N)~, viên bi thứ ~i~ có khối lượng là ~w_i~ và có giá trị là ~v_i~.

~Kaninho~ quyết định chọn một số viên bi trong ~N~ viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là ~W~, có nghĩa là tổng khối lượng của các viên bi được chọn không được vượt quá ~W~.

Hãy tìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.

Input

• Dòng thứ nhất chứa hai số nguyên ~N, W~ ~(1 \le N \le 100,\ 1 \le W \le 10^9)~
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~w_i, v_i~ ~(1 \le w_i \le W,\ 1 \le v_i \le 10^3)~

Output

• In ra giá trị lớn nhất tìm được

Sample

Input #1

3 8
3 30
4 50
5 60

Output #1

90

Input #2

1 1000000000
1000000000 10

Output #2

10

Input #3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Output #3

17

Hint

Ở sample test 1, các viên bi thứ ~1~ và ~3~ sẽ được chọn để bỏ vào ba lô. Tổng khối lượng của chúng không vượt quá ~8~ và tổng giá trị đạt lớn nhất là ~90~.

Problem source: DP Contest AtCoder