## JDCC '15 Contest 4 P5 - Pocket Change

View as PDF

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

Author:
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 cents
2. She gives the grocer cents
3. The grocer gives back cents in the most efficient manner possible

For example, if Rosie is in Canada, her total is , and Rosie has nickels and quarters, she can give the grocer nickels and two quarters . The grocer would then give her a dime in change. This way, Rosie is able to get rid of coins, leaving her with in total.

Rosie has perfected this technique for Canada, however she loves to travel and wants to maximize her coin lossage everywhere. Given the types of coins the grocer has (assume the grocer has more than enough of every coin), the coins that Rosie has, and her total , 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, . test cases follow. Each test case begins with three integers .

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

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

Note: For the first of cases, .

#### 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

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

#### Sample Output

2
5

#### 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 coin. Then, the grocer optimally gives her cents in change using three coins, one coin and one coin. Hence, Rosie is left with coins.