AT_ndpc2026_n ナップサック

$ N $ 種類の品物がそれぞれ無数にあります。 $ i $ 種類目の品物は重さ $ i $ 、価値 $ v_i $ です。 $ Q $ 個のクエリに答えてください。各クエリでは正整数 $ W $ が与えられるので、重さの総和がちょうど $ W $ になるように品物を集めた時の、集めた品物の価値の総和としてあり得る最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ v_1 $ $ v_2 $ $ \dots $ $ v_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ W $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリの答えを出力せよ。

### 注意 この問題は他の問題に比べてマニアックな知識を問う問題です。 満点解法に心当たりの無い方は部分点が取れたら次の問題に行くことを推奨します。 ### 部分点 この問題には部分点が設定されている。 - $ N \leq 300 $ であるデータセットに正解した場合、 $ 4 $ 点が与えられる。 ### Sample Explanation 1 例えば $ 6 $ 番目のクエリでは $ W=6 $ です。この時、 $ 3 $ 種類目の品物を $ 2 $ 個集めると価値の総和は $ 7 + 7 = 14 $ になり、これが最大です。 ### Constraints - $ 1 \leq N \leq 4000 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 0 \leq v_i \leq 10^9 $ - $ 1 \leq W \leq 10^9 $ - 入力される値は全て整数