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 分。 ## 样例解释 1 例如，在第六个询问中，$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$ - 所有输入均为整数。 由 ChatGPT 5 翻译