問題文

食堂に来たYさんは、何を食べようか迷っている。この食堂のメニューには $N$ 種類の料理があり、$i(1 \leq i \leq N)$番目の料理の値段は$c_i$円で、Yさんはこれを食べると幸福度が$h_i$だけ増加する。ここで、Yさんは予算$C$円でできるだけ多くの幸福度が得られるように料理を頼みたい。ただし、同じ種類の料理はそれぞれ1つしか頼んではいけないものとする。予算を超えないよう適切に料理を頼んだ際、得られる幸福度の最大値を求めよ。

制約

• $1 \leq N \leq 10^3$
• $1 \leq C,c_i \leq 10^3$
• $1 \leq h_i \leq 10^9$

入力

入力はすべて整数である。

N C
c_1 h_1
c_2 h_2
...
c_N h_N

出力

計算結果を一行に出力せよ。

サンプル

3 3
1 2
3 3
2 2

4

料理$1,3$を頼むと幸福度が$4$となり、これが最適です。

5 10
3 8
2 1
4 9
8 12
10 100

100

料理$5$を頼むと幸福度が$100$となり、これが最適です。