問題
情報処理部に所属するれんさんは、部活中にも関わらずお腹が空きました。れんさんはお腹が空いていて動けません。そこで れんさんは、後輩に「おかし買ってきてね。お金払うから。」と伝えて購買に「おかし」を買いに行かせました。
購買にはたくさんの「おかし」が売られています。それぞれの「おかし」には値段と満腹度が決まっています。ある「おかし」を食べると、その満腹度だけ、れんさんのお腹が満たされます。
後輩たちは、れんさんになるべく多くお金を払わそうと企みました。具体的には、れんさんのお腹の容量以下になるように「おかし」を購入したとき、値段の合計の最大となるようにします。このときの値段の合計の最大値を求めてください。
入力
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 番目の「おかし」を選ぶと、れんさんのお腹の容量を上回るので買えません。