JDCC '15 Contest 4 P5 - Pocket Change

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 64M

Problem type

Rosie hates nothing more than carrying change. As a result, whenever she goes shopping she uses the opportunity to get rid of as much change as she can. She does this as follows:

  1. Her total comes out to K cents
  2. She gives the grocer K+L cents
  3. The grocer gives back L cents in the most efficient manner possible

For example, if Rosie is in Canada, her total is K = 60, and Rosie has 4 nickels and 3 quarters, she can give the grocer 4 nickels and two quarters (K+L = 70). The grocer would then give her a dime (L = 10) in change. This way, Rosie is able to get rid of 5 coins, leaving her with 2 in total.

Rosie has perfected this technique for Canada, however she loves to travel and wants to maximize her coin lossage everywhere. Given the N types of coins the grocer has (assume the grocer has more than enough of every coin), the M coins that Rosie has, and her total K, find the minimum number of coins she can have after the transaction.

Input Specification

The first line of the input provides the number of test cases, T (1 \le T \le 100). T test cases follow. Each test case begins with three integers N, M, K (1 \le N, M \le 100, 1 \le K \le 1 000).

The next line contains N integers, the types of coins that the grocer has. Each of the grocer's coins will have a value that is less than 10 000 and the grocer is able to give out any amount of change.

The line after that contains M integers, the coins that Rosie has (she has one of each). The total value of all her coins will be between K and 10 000.

Note: For the first 50\% of cases, M = 1.

Output Specification

For each test case, your program should output one integer: the minimum number of coins that Rosie can have after the transaction.

Sample Input

5 7 60
5 10 25 100 200
5 5 5 5 25 25 25
5 1 100
1 9 12 19 24

Sample Output


Explanation of Sample

The first case is described in the problem statement. In the second case, Rosie has no choice except to give grocer her 200 coin. Then, the grocer optimally gives her 100 cents in change using three 24 coins, one 19 coin and one 9 coin. Hence, Rosie is left with 5 coins.


There are no comments at the moment.