005 - れんさんが食べたい！(陰謀)

問題

情報処理部に所属するれんさんは、部活中にも関わらずお腹が空きました。れんさんはお腹が空いていて動けません。そこで れんさんは、後輩に「おかし買ってきてね。お金払うから。」と伝えて購買に「おかし」を買いに行かせました。

購買にはたくさんの「おかし」が売られています。それぞれの「おかし」には値段と満腹度が決まっています。ある「おかし」を食べると、その満腹度だけ、れんさんのお腹が満たされます。

後輩たちは、れんさんになるべく多くお金を払わそうと企みました。具体的には、れんさんのお腹の容量以下になるように「おかし」を購入したとき、値段の合計の最大となるようにします。このときの値段の合計の最大値を求めてください。

入力

N U
S1 V1
S2 V2
:
SN VN

1 行目に、購買に売られている「おかし」の数 N と、れんさんのお腹の容量 U が与えられる。

2 行目から N 行にかけて、それぞれの「おかし」の情報が与えられる。このうち i 行目は、「おかし」i の値段が S_i で 満腹度が V_i であることを意味する。ただし「おかし」は、1 つの情報につき 1 つで買ったら無くなる。

制約

• 1 ≦ N ≦ 100
• 1 ≦ U ≦ 10⁹
• 1 ≦ S_i ≦ 100
• 1 ≦ V_i ≦ 10⁷

出力

1 行に、れんさんのお腹の容量以下となるように「おかし」を購入したときの、値段の合計の最大値を出力せよ。

入出力例

入力例1

4 5
3 2
2 1
4 3
2 2

出力例1

7

1, 2, 4 番目の「おかし」を選ぶと、満腹度は 3 + 2 + 2 = 7 となり、これが最大値となります。

入力例2

1 1
33 4

出力例2

0

1 番目の「おかし」を選ぶと、れんさんのお腹の容量を上回るので買えません。