注意

本题相比其他题目会用到更偏门的知识。如果暂时想不到满分做法，建议取得部分分后先继续完成后面的题目。

题目描述

有 $N$ 种物品，每种物品都有无限多个。第 $i$ 种物品的重量为 $i$，价值为 $v_i$。

回答 $Q$ 个询问。每个询问给出一个正整数 $W$，请选择若干物品，使它们的总重量恰好为 $W$，并求能够取得的最大总价值。

限制条件

• $1\le N\le 4000$
• $1\le Q\le 2\times 10^5$
• $0\le v_i\le 10^9$
• $1\le W\le 10^9$
• 所有输入均为整数。

部分分

• 对满足 $N\le 300$ 的数据求解正确，可获得 $4$ 分。

输入

N Q
v_1 v_2 ... v_N
W_1
W_2
...
W_Q

输出

输出 $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$ 种物品时，总价值为 $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