← 返回题目列表

Codeforces · 1676/E

E. 饮食查询

中文机器翻译题面 查看原题

Timur 有 $$$n$$$ 糖果。第 $$$i$$$ 糖果的糖含量等于 $$$a_i$$$。因此,通过吃第 $$$i$$$ 糖果,Timur 消耗的糖量等于 $$$a_i$$$。

Timur 会询问你关于他的糖果的 $$$q$$$ 问题。对于第 $$$j$$$ 查询,您必须回答他需要吃的最小糖果数量是多少,才能达到大于或等于 $$$x_j$$$ 的糖量,如果无法获得这样的数量,则打印 -1。换句话说,您应该打印最小可能的 $$$k$$$,这样在吃完 $$$k$$$ 糖果后,Timur 消耗的糖量至少为 $$$x_j$$$,或者说不存在可能的 $$$k$$$。

请注意,他不能吃两次相同的糖果,并且查询是相互独立的(Timur 可以在不同的查询中使用相同的糖果)。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。

第一行包含 $$$2$$$ 整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 1.5\cdot10^5$$$) - Timur 拥有的糖果数量和您必须分别打印答案的查询数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^4$$$) — 分别是每种糖果中的糖含量。

然后是 $$$q$$$ 行。

接下来的 $$$q$$$ 行都包含一个整数 $$$x_j$$$ ($$$1 \leq x_j \leq 2 \cdot 10^9$$$) – Timur 对于给定查询想要达到的数量。

保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和不超过 $$$1.5 \cdot 10^5$$$。

输出

对于每个测试用例输出 $$$q$$$ 行。对于第 $$$j$$$ 行输出,Timur 需要吃多少糖果才能达到大于或等于 $$$x_j$$$ 的糖量,如果无法获得这样的数量,则打印 -1。

示例

输入 #1

3
8 7
4 3 3 1 1 4 5 9
1
10
50
14
15
22
30
4 1
1 2 3 4
3
1 2
5
4
6

输出 #1

1
2
-1
2
3
4
8
1
1
-1

注意

对于第一个测试用例:

对于第一个查询,Timur 可以吃任何糖果,并且他会达到所需的数量。

对于第二个查询,Timur 通过吃第 $$$7$$$ 和第 $$$8$$$ 糖果可以达到至少 $$$10$$$ 的数量,从而消耗相当于 $$$14$$$ 的糖量。

对于第三个查询,没有可能的答案。

对于第四个查询,Timur 通过吃第 $$$7$$$ 和第 $$$8$$$ 糖果可以达到至少 $$$14$$$ 的数量,从而消耗等于 $$$14$$$ 的糖量。

对于第二个测试用例:

对于第二个测试用例的唯一查询,我们可以选择 Timur 从中恰好收到 $$$3$$$ 糖的第三颗糖果。选择第四颗糖果也可以获得相同的答案。