A young mage, determined to master his craft, has collected n magical potions. Each potion contains a fixed amount of mana energy, but their strengths differ. The i-th potion is infused with exactly pi mana points.
The Tower Master, eager to test the mage’s efficiency, asks him q questions. Each question is the same challenge, “If you must gather at least qi mana, what is the smallest number of potions you must drink?”
A potion cannot be used more than once in a single question.
However, every question is independent, so the mage can reuse the same potion in different questions.
If it is impossible to reach the required mana qi, answer with -1.
Constraints
1 ≤ t ≤ 1000
1 ≤ n, q ≤ 150,000
1 ≤ pi ≤ 10,000
1 ≤ qi ≤ 2 × 10^9
Input Format
The first line of input contains a single number t: the number of test cases
For each test case:
The first line contains two numbers: n (the number of potions) and q (the number of questions).
The next line contains array p with n numbers, where the i-th number pi is the mana inside the i-th potion.
The third line contains q numbers, where the i-th number qi is the ith question.
Output Format
For every question, print the smallest number of potions required to gather at least qi mana on a new line. If not possible, print -1.
Example 1
Input:
2
5 3
3 8 1 1 2
11 16 2
1 2
5
4 6
Output:
2
-1
1
1
-1
Explanation:
For test case 1, the mage can get at least 11 mana points by drinking the 8 and 3 potion but cannot get 16 mana points. The mage can get at least 2 mana points by drinking the 2 potion.
For test case 2, the mage can get at least 4 mana points by drinking the 5 point potion but cannot get 6 mana points.
Log In to solve the Question