Angie is going shopping!
She has different types of coins in her pocket, with the type of coin being worth dollars, and she's going to stores. From the store, she wants to buy dollars worth of stuff from store , but store only accepts the first types of coins in her pocket!
Can you help her figure out the minimum number of coins to pay for each transaction in exact change?
Note that for the purpose of this problem, Angie has an infinite number of each type of coin.
Constraints
Input Specification
The first line of input consists of and , separated by a space.
The next line contains space separated integers containing the values ().
The next lines of input each contain the space separated integers and .
Output Specification
There are lines of output, with each line containing the minimum amount of coins needed to satisfy the payment in the transaction.
If the transaction cannot be satisfied however, print -1
.
Note for Python users: To pass this question using Python you must select the PyPy interpreter instead of the normal one.
Sample Input 1
6 3
7 10 15 2 3 24
107 3
12 4
24 2
Sample Output 1
8
2
3
Explanation
Transaction 1: coins with , coin with , and coin worth .
Transaction 2: coin worth , and coin worth .
Transaction 3: coin worth , and coins worth .
All that needs to be noted here is that for the third transaction, even though she has a coin worth the third store won't accept it.
Sample Input 2
4 3
11 15 3 1
6 2
15 1
7 4
Sample Output 2
-1
-1
3
Explanation
Transactions 1 and 2: Not possible.
Transaction 3: coins worth , and coin worth .
Note that the first transaction cannot be completed without the third type of coin and the second one cannot be completed without the second type of coin.
Comments
Please note that the test data for this problem is different then on the other judges. If you believe that the data is incorrect, feel free to ask about it on the discord server.
Partials will not be enabled for this problem (the batches were a unintended consequence of how the data was generated).