Nuts

個の木の実があります。
個目の木の実は、 グラムの重さがあり、食べると攻撃力が だけ上昇します。

また、 体のモンスターがいます。
体目のモンスターは、木の実を食べる前の攻撃力は で、木の実を グラムまで食べることができます。

それぞれのモンスターについて、木の実をあげた時に得られる攻撃力の最大値を求めてください。

• 入力はすべて整数である。

入力は以下の形式で標準入力から与えられる。

N M
A1 A2 …… AN
B1 B2 …… BM

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

5 3
2 5 1 3 6
2 10 17

1 3 5

• 体目のモンスターは、重さが の木の実を食べることによって攻撃力を にすることができます。
• 体目のモンスターは、重さが の木の実を食べることによって攻撃力を にすることができます。
• 体目のモンスターは、全ての木の実を食べることができるので、攻撃力を にすることができます。

10 6
74 36 84 97 28 40 38 29 64 65 
736 351 837 970 273 395 

10 7 10 10 6 8