Eating Queries
Contest: Codeforces Round 790 (Div. 4)
Difficulty rating: 1100
Tags: binary search, greedy, sortings

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).

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 3.5 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
1
2
-1
2
3
4
8
1
1
-1

Editorial:
Let's solve the problem with just one query. Greedily, we should pick the candies with the most sugar first, since there is no benefit to picking a candy with less sugar.
So the solution is as follows: sort the candies in descending order, and then find the prefix whose sum is $$$\geq x$$$. This is $$$\mathcal{O}(n)$$$ per query, which is too slow for us.
To speed it up, notice that we just need to find a prefix sum at least $$$x$$$. So if we compute the prefix sums of the reverse-sorted array, we need to find the first element that is at least $$$x$$$.
Since all elements of $$$a$$$ are positive, the array of prefix sums is increasing. Therefore, you can binary search the first element $$$\geq x$$$. This solves the problem in $$$\log n$$$ per query.
Total time complexity: $$$\mathcal{O}(q \log n + n)$$$.