問題文

NN 個のお菓子があります。
ii 個目のお菓子は、AiA_{i} グラムの重さがあり、食べると BiB_{i} カロリーを摂取することができます。
やきとりくんは、お菓子を食べてなるべくカロリーを摂取しようと思っています。
しかし、やきとりくんは胃の大きさが小さいので、食べ物を合計で KK グラムまでしか食べることができません。
やきとりくんが摂取できるカロリーの最大値を求めてください。

制約

  • 1N1001 \leq N \leq 100
  • 1K1091 \leq K \leq 10^9
  • 1Ai109(1iN)1 \leq A_{i} \leq 10^9 \: (1 \leq i \leq N)
  • 1Bi103(1iN)1 \leq B_{i} \leq 10^3 \: (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N K
A1 A2 ...... AN
B1 B2 ...... BN

出力

問題の答えを一行に出力せよ。

入出力例

入力例1
3 10
2 5 8
10 40 45
出力例1
55

11 番目のお菓子と 33 番目のお菓子を食べると、10+45=5510 + 45 = 55 カロリーを摂取することができ、これが最大値となります。

入力例2
10 356
41 41 93 83 25 36 79 45 85 49
182 522 900 878 309 871 56 934 895 783
出力例2
4905

提出


Go (1.21)