CF1676E Eating Queries

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$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 1.5 \cdot 10^5$），分别表示 Timur 拥有的糖果数量和你需要回答的问题数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^4$），分别表示每颗糖果的糖分含量。 接下来 $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$。

对于第一个测试用例： 对于第一个问题，Timur 吃任意一颗糖果即可达到目标糖分。 对于第二个问题，Timur 可以吃第 $7$ 颗和第 $8$ 颗糖果，总共摄入 $14$ 单位糖分，达到目标。 对于第三个问题，没有办法达到目标糖分。 对于第四个问题，Timur 可以吃第 $7$ 颗和第 $8$ 颗糖果，总共摄入 $14$ 单位糖分，达到目标。 对于第二个测试用例： 对于该测试用例的唯一一个问题，我们可以选择第三颗糖果，Timur 恰好摄入 $3$ 单位糖分。也可以选择第四颗糖果，结果相同。 由 ChatGPT 4.1 翻译