F-茶包博弈

题目描述

在扑克桌上，有 $N$ 种不同口味的茶包。口味编号为 $1$ 到 $N$，第 $i$ 种口味有 $A_i$ 个茶包（$1 \leq i \leq N$）。

你将用这些茶包玩一个游戏。该游戏有一个称为难度的参数，取值范围为 $1$ 到 $A_1 + \dots + A_N$（包含端点）。难度为 $b$ 的游戏流程如下：

1. 你选择一个整数 $x$，其中 $b \leq x \leq A_1 + \dots + A_N$。
2. 庄家从桌上的茶包中选出恰好 $x$ 个茶包交给你。
3. 你检查这 $x$ 个茶包的口味，并从中选出 $b$ 个茶包。
4. 如果你选出的 $b$ 个茶包全部为同一口味（来源于同一个$A_i$），则你获胜；否则你失败。

庄家会尽全力让你失败。

你会得到 $Q$ 个询问，请分别回答。第 $j$ 个询问如下：

• 对于难度为 $B_j$ 的游戏，报告你必须在开始时选择的最小整数 $x$，以保证获胜。如果无法获胜，则输出 $-1$。

输入格式

输入按如下格式给出：

$N$ $Q$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$
$\vdots$
$B_Q$

输出格式

输出 $Q$ 行。

第 $j$ 行（$1 \leq j \leq Q$）应输出第 $j$ 个询问的答案。

输入输出样例 #1

输入 #1

4 5
4 1 8 4
1
8
5
2
10

输出 #1

1
17
14
5
-1

输入输出样例 #2

输入 #2

5 3
13 13 13 13 2
5
12
13

输出 #2

19
47
51

说明/提示

样例解释 1

对于第 $1$ 个询问，如果你选择 $x=1$，那么无论庄家选哪一个茶包，你都可以通过选择这一个茶包来满足获胜条件。由于 $x$ 不能小于 $1$，所以答案是 $1$。

对于第 $2$ 个询问，如果你选择 $x=17$，那么无论庄家选哪 $17$ 个茶包，你都可以通过选择合适的 $8$ 个茶包来满足获胜条件。反之，如果 $x < 17$，庄家可以选择茶包使你无法获胜。因此，答案是 $17$。

对于第 $3$ 个询问，如果你选择 $x=14$，那么无论庄家选哪 $14$ 个茶包，你都可以通过选择合适的 $5$ 个茶包来满足获胜条件。反之，如果 $x < 14$，庄家可以选择茶包使你无法获胜。因此，答案是 $14$。

对于第 $4$ 个询问，如果你选择 $x=5$，那么无论庄家选哪 $5$ 个茶包，你都可以通过选择合适的 $2$ 个茶包来满足获胜条件。反之，如果 $x < 5$，庄家可以选择茶包使你无法获胜。因此，答案是 $5$。

对于第 $5$ 个询问，无论你选择什么 $x$，庄家都可以选择茶包使你无法获胜。因此，输出 $-1$。

数据范围

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq Q \leq 3 \times 10^5$
• $1 \leq A_i \leq 10^6$（$1 \leq i \leq N$）
• $1 \leq B_j \leq \min(10^6, A_1 + \dots + A_N)$（$1 \leq j \leq Q$）
• 所有输入均为整数。