問題文
わりとねこくんは、所持金 円を握りしめて猫缶専門店「にゃいすふ〜ど」へやってきました。
にゃいすふ〜どでは 個の猫缶が売られており、 番目の猫缶は価格が 円で、大きさが です。
わりとねこくんは、購入する猫缶の価格の合計が所持金 円以下となるように、いくつか猫缶を選んで買おうとしています。
ただし、各猫缶は つずつしか売られていないため、同じ猫缶を複数個買うことはできません( 個も買わないことも可能です)。
わりとねこくんが買うことのできる猫缶の大きさの合計の最大値を求めてください。
制約
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
出力
購入できる猫缶の大きさの合計の最大値を 行に出力してください。
サンプル 1
入力
10 4
6 13
5 10
5 10
4 6
出力
20
たとえば、 個目の猫缶を 円で買うことができ、このときの猫缶の大きさの総和は です。 これ以上大きさの総和を大きくすることはできないため、 を出力します。
サンプル 2
入力
7 3
4 9
5 10
6 11
出力
11
サンプル 3
入力
4 4
1 1000000000
1 1000000000
1 1000000000
1 1000000000
出力
4000000000
参加受付は終了しました。
ログインして解答を提出
解答の提出や採点結果の確認には、ログインが必要です。
ログインする