CF1676E.Eating Queries

Timur has $n$ candies. The $i$-th candy has a quantity of sugar equal to $a_i$. So, by eating the $i$-th candy, Timur consumes a quantity of sugar equal to $a_i$.

Timur will ask you $q$ queries regarding his candies. For the $j$-th query you have to answer what is the minimum number of candies he needs to eat in order to reach a quantity of sugar greater than or equal to $x_j$ or print -1 if it's not possible to obtain such a quantity. In other words, you should print the minimum possible $k$ such that after eating $k$ candies, Timur consumes a quantity of sugar of at least $x_j$ or say that no possible $k$ exists.

Note that he can't eat the same candy twice and queries are independent of each other (Timur can use the same candy in different queries).

蒂穆尔有 $n$ 颗糖果。第 $i$ 颗糖果含糖量为 $a_i$。因此，吃掉第 $i$ 颗糖果会使蒂穆尔摄入 $a_i$ 单位的糖。

蒂穆尔将向你提出 $q$ 个关于这些糖果的查询。对于第 $j$ 个查询，你需要回答：他至少需要吃掉多少颗糖果，才能使总摄入糖量大于等于 $x_j$；若无法达到该糖量，则输出 -1。换言之，你需要找出最小的可能值 $k$，使得吃掉 $k$ 颗糖果后，蒂穆尔摄入的总糖量至少为 $x_j$；若不存在这样的 $k$，则说明无法实现。

注意：每颗糖果最多只能吃一次；且各查询相互独立（即蒂穆尔可在不同查询中重复使用同一颗糖果）。

The first line of input contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of test cases follows.

The first line contains $2$ integers $n$ and $q$ ($1 \leq n, q \leq 1.5\cdot10^5$) — the number of candies Timur has and the number of queries you have to print an answer for respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^4$) — the quantity of sugar in each of the candies respectively.

Then $q$ lines follow.

Each of the next $q$ lines contains a single integer $x_j$ ($1 \leq x_j \leq 2 \cdot 10^9$) – the quantity Timur wants to reach for the given query.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $1.5 \cdot 10^5$.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。随后是各测试用例的描述。

第一行包含两个整数 $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$。

For each test case output $q$ lines. For the $j$-th line output the number of candies Timur needs to eat in order to reach a quantity of sugar greater than or equal to $x_j$ or print -1 if it's not possible to obtain such a quantity.

对于每个测试用例，输出 $q$ 行。第 $j$ 行输出 Timur 需要吃的糖果数量，使得其摄入的糖分总量大于等于 $x_j$；若无法达到该糖分总量，则输出 -1。

For the first test case:

For the first query, Timur can eat any candy, and he will reach the desired quantity.

For the second query, Timur can reach a quantity of at least $10$ by eating the $7$-th and the $8$-th candies, thus consuming a quantity of sugar equal to $14$.

For the third query, there is no possible answer.

For the fourth query, Timur can reach a quantity of at least $14$ by eating the $7$-th and the $8$-th candies, thus consuming a quantity of sugar equal to $14$.

For the second test case:

For the only query of the second test case, we can choose the third candy from which Timur receives exactly $3$ sugar. It's also possible to obtain the same answer by choosing the fourth candy.

对于第一个测试用例：

对于第一个查询，Timur 可以吃任意一颗糖果，即可达到目标糖分量。

对于第二个查询，Timur 可通过吃第 7 颗和第 8 颗糖果，使摄入的糖分总量至少达到 $10$，此时消耗的糖分总量为 $14$。

对于第三个查询，不存在可行解。

对于第四个查询，Timur 可通过吃第 7 颗和第 8 颗糖果，使摄入的糖分总量至少达到 $14$，此时消耗的糖分总量为 $14$。

对于第二个测试用例：

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