/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 6 点
注意
この問題は他の問題に比べてマニアックな知識を問う問題です。
満点解法に心当たりの無い方は部分点が取れたら次の問題に行くことを推奨します。
問題文
N 種類の品物がそれぞれ無数にあります。i 種類目の品物は重さ i、価値 v_i です。
Q 個のクエリに答えてください。各クエリでは正整数 W が与えられるので、重さの総和がちょうど W になるように品物を集めた時の、集めた品物の価値の総和としてあり得る最大値を求めてください。
制約
- 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
- 入力される値は全て整数
部分点
この問題には部分点が設定されている。
- N \leq 300 であるデータセットに正解した場合、4 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N Q
v_1 v_2 \dots v_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各クエリは以下の形式で与えられる。
W
出力
Q 行出力せよ。i 行目には i 番目のクエリの答えを出力せよ。
入力例 1
4 9 2 1 7 4 1 2 3 4 5 6 7 8 9
出力例 1
2 4 7 9 11 14 16 18 21
例えば 6 番目のクエリでは W=6 です。この時、3 種類目の品物を 2 個集めると価値の総和は 7 + 7 = 14 になり、これが最大です。
入力例 2
10 10 104 231 361 478 661 765 963 1132 1402 1552 1 10 15 27 48 100 853822501 687675302 281611653 844033520
出力例 2
104 1552 2213 4206 7460 15572 133006571782 107124530332 43868837466 131481666104
Score : 6 points
Note
This problem requires more specialized knowledge compared to the others.
If you do not have an idea for a full solution, it is recommended to aim for partial points and then move on to the next problem.
Problem Statement
There are infinitely many items of each of N types. The i-th type of item has weight i and value v_i.
You are given Q queries. In each query, you are given a positive integer W.
Find the maximum possible total value when you choose some items such that the total weight is exactly W.
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
- All input values are integers
Partial Score
This problem has partial scoring.
- If you solve the dataset with N \leq 300, you will get 4 points.
Input
The input is given from standard input in the following format:
N Q
v_1 v_2 \dots v_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is given in the following format:
W
Output
Print Q lines. On the i-th line, output the answer for the i-th query.
Sample Input 1
4 9 2 1 7 4 1 2 3 4 5 6 7 8 9
Sample Output 1
2 4 7 9 11 14 16 18 21
For example, in the 6th query, W=6.
If you take two items of type 3, the total value becomes 7 + 7 = 14, which is the maximum.
Sample Input 2
10 10 104 231 361 478 661 765 963 1132 1402 1552 1 10 15 27 48 100 853822501 687675302 281611653 844033520
Sample Output 2
104 1552 2213 4206 7460 15572 133006571782 107124530332 43868837466 131481666104