012 - うっちーとうっちーのおかいもの

問題

うっちー(woody_1227)とうっちー(gousuper)は2人でお買い物にきました。
2人の所持金の合計は$M$円で、それを超えないようになるべく満足度の高い買い物をしたいと思っています。
そのお店には$N$個の商品があり、$i$番目の商品の値段は$Cost_i$円、その商品を買った時に増える満足度は$Value_i$です。
所持金の合計を超えないように買い物をしたときの満足度の合計の最大値を出力してください。
買い物前の満足度は$0$とします。

入力

$N$ $M$
$Cost_0$ $Value_0$
$Cost_1$ $Value_1$
$Cost_2$ $Value_2$
:
$Cost_{N-1}$ $Value_{N-1}$

出力

問題文のとおり

制約

全ての入力において以下を満たす。

• $1 ≤ N ≤ 20$
• $1 ≤ M ≤ 10^{18}$
• $1 ≤ Cost_i ≤ 10^9$
• $-10^9 ≤ Value_i ≤ 10^9$

入出力例

入力例1

4 100
50 6
60 9
40 3
10 4

出力例1

13

1つ目、3つ目、4つ目の商品を買うと、満足度が最大になります。

入力例2

3 50
60 9
110 2
89 1227

出力例2

0

お金が足りなくて何も買えないことも...

入力例3

5 114514
10 -810
20 -364364
30 -1210
40 -316
50 -1919

出力例3

0

買うと不満になる可能性もあります。
返品はできないので買わないようにしましょう。

---