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

時間制限 1 秒 / メモリ制限 64 MB / 得点 400 / x 0 /


TLE
1sec
MLE
64MB
得点
400

問題

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

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

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

入力

N U
S1 V1
S2 V2
:
SN VN

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

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

制約

  • 1 ≦ N ≦ 100
  • 1 ≦ U ≦ 109
  • 1 ≦ Si ≦ 100
  • 1 ≦ Vi ≦ 107

出力

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 番目の「おかし」を選ぶと、れんさんのお腹の容量を上回るので買えません。