問題
情報処理部に所属するれんさんは、部活中にも関わらずお腹が空きました。れんさんはお腹が空いていて動けません。そこで れんさんは、後輩に「おかし買ってきてね。お金払うから。」と伝えて購買に「おかし」を買いに行かせました。
購買にはたくさんの「おかし」が売られています。それぞれの「おかし」には値段と満腹度が決まっています。ある「おかし」を食べると、その満腹度だけ、れんさんのお腹が満たされます。
後輩たちは、れんさんになるべく多くお金を払わそうと企みました。具体的には、れんさんのお腹の容量以下になるように「おかし」を購入したとき、値段の合計の最大となるようにします。
れんさんは、この話を聞いて驚きました。どうも、お金が減るわけです。これでは面白くないので、れんさんは不断の努力と気合によって、自分のお腹の容量を可変にしました。ただし、「おかし」をたくさん食べたいことには変わりありません。そこで、後輩に買われる「おかし」の値段の合計が X 以下となるような、最大のお腹の容量を求めることにしました。
入力
N X S1 V1 S2 V2 : SN VN
1 行目に、購買に売られている「おかし」の数 N と、れんさんのお金の上限 X が与えられる。
2 行目から N 行にかけて、それぞれの「おかし」の情報が与えられる。このうち i 行目は、「おかし」i の値段が Si で 満腹度が Vi であることを意味する。ただし「おかし」は、1 つの情報につき 1 つで買ったら無くなる。
制約
- 1 ≦ N ≦ 100
- 1 ≦ X ≦ 109
- 1 ≦ Si ≦ 107
- 1 ≦ Vi ≦ 100
出力
1 行に、後輩に買われる「おかし」の値段の合計が X 以下となるように、れんさんのお腹の容量を定めるとき、お腹の容量の最大値を出力せよ。
ただし、お腹の容量をいくら増やしても、「おかし」の値段の合計が X 以下となることがある。そのときには、"inf" を 1 行に出力せよ。
入出力例
入力例1
4 7 3 2 2 1 4 3 2 2
出力例1
5
値段の合計が 7 以下となるように後輩に買わせるためには、お腹の容量を 5 にすると良いです。お腹の容量を 5 にしたとき、後輩は 1, 2, 4 番目の「おかし」を購入するので、値段の合計はちょうど 7 となります。お腹の容量を 6 にすると、後輩が買う「おかし」の値段の合計は、9 となってしまいます。
入力例2
1 1 33 4
出力例2
3
お腹の容量を 4 とすると、1 番目の「おかし」を買えて、お金の上限 1 を上回るのでしまうので、3 を出力します。
入力例2
1 33 33 4
出力例2
inf
お腹の容量をいくら増やしても、お金の上限 33 を上回らないので "inf" を出力します。