AT_ndpc2026_n.Knapsack

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$.

共有 $N$ 种物品，每种物品的数量均为无限。第 $i$ 种物品的重量为 $i$，价值为 $v_i$。

你将收到 $Q$ 个查询。在每个查询中，你将获得一个正整数 $W$。
请找出在所选物品总重量恰好为 $W$ 的前提下，所能达到的最大总价值。

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$

输入从标准输入中按以下格式给出：

$N$ $Q$
$v_1$ $v_2$ $\dots$ $v_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询按以下格式给出：

$W$

Print $Q$ lines. On the $i$-th line, output the answer for the $i$-th query.

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

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.### Partial Score

This problem has partial scoring.

• If you solve the dataset with $N \leq 300$, you will get $4$ points.

Sample 1 Explanation:
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.

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

注意

本题相较于其他题目需要更专业的知识。
若您尚未想到完整解法，建议先争取部分分，然后继续下一题。

部分分

本题设有部分分。

• 若您解决了满足 $N \leq 300$ 的数据集，则可获得 $4$ 分。

样例 1 解释：
例如，在第 6 次查询中，$W=6$。
若选取两个类型为 $3$ 的物品，则总价值为 $7 + 7 = 14$，此为最大值。

限制条件

• $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$
• 所有输入值均为整数