時間制限 : sec, メモリ制限 : KB
English / Japanese  

巨大ナップザック問題

価値が vi 重さが wi であるような N 個の品物と、容量が W のナップザックがあります。次の条件を満たすように、品物を選んでナップザックに入れます:

  • 選んだ品物の価値の合計をできるだけ高くする。
  • 選んだ品物の重さの総和は W を超えない。

価値の合計の最大値を求めてください。

入力

N W
v1 w1
v2 w2
:
vN wN

1行目に2つの整数 NW が空白区切りで1行に与えられます。 続く N 行に i 番目の品物の価値 vi と重さ wi が空白区切りで与えられます。

出力

価値の合計の最大値を1行に出力してください。

制約

  • 1 ≤ N ≤ 40
  • 1 ≤ vi ≤ 1015
  • 1 ≤ wi ≤ 1015
  • 1 ≤ W ≤ 1015

入出力例


入力例 1

4 5
4 2
5 2
2 1
8 3

出力例 1

13

入力例 2

2 20
5 9
4 10

出力例 2

9