本の購入
店には
n 冊の本があり、それぞれの本について価格とページ数がわかっています。あなたの手元には x ドルしかないので、使える金額は最大で x ドルまでに限られます。購入は各本につき一度きりしかできません。与えられた予算内で、合計ページ数をできるだけ多くするにはどうすればよいでしょうか。入力
1 行目には、
n (1 ≤ n ≤ 100) と x (1 ≤ x ≤ ) の 2 つの整数が入力として与えられます。次の行には
n 個の整数 (1 ≤ ≤ 1000) が空白区切りで与えられます。これは各本の価格を表します。3 行目には
n 個の整数 (1 ≤ ≤ 1000) が空白区切りで与えられます。これは各本のページ数を表します。出力
予算
x ドルを使って買える本の合計ページ数の最大値を出力してください。例
入力 | 出力 |
4 10
4 8 5 3
5 12 8 1 | 13 |
解説
最初の本と 3 冊目の本を買うと、支払額は
4 + 5 = 9、合計ページ数は 5 + 8 = 13 となります。Constraints
Time limit: 7 seconds
Memory limit: 512 MB
Output limit: 1 MB