Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3912
Coins

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Darksun loves traveling very much, especially when there are many delicious snacks in the place where he travels. Darksun is not wealthy but he is very clever. In oder to taste more kinds of yummy snacks with limited money, Darksun used many ways to save money such as taking bus and taking underground. As a result, he always pays attention to collecting coins during the trip because coins are necessary when taking bus or underground.

However, during his last trip in Japan, he received an urgent phone call from ZJU, telling him to go back and attend the ACM training. He felt very sad when hearing the message. The saddest part was that he had collected thousands of coins which were extremely heavy. In order to carry fewer coins when boarding the plane, clever Darksun decided to use as many coins as possible to buy a nice Garage Kits(GK) because he loves Japanese cartoons so much.

There are only 6 kinds of coins, which are 1, 5, 10, 50 and 100. Now, we know that Darksun has a $1 coins, b $5 coins, c $10 coins, d $50 coins, e $100 coins and f $500 coins.

The GK that Darksun wanted to buy costs $p. It is ok for Darksun to give more money than $p to the cashier. If Darksun gives $q (q > p) to the cashier, the cashier will return $(q-p) using the fewest number of coins. For example, if q=100 and p=91 the cashier will give Darksun one $5 coin and four $1 coins.

Notice: However, it is invalid when any partial sum of the coins that Darksun gives to the cashier is equal to one of the coins' value that the cashier returns to him.
For example, if Darksun gives 101 coins of value 1 to the cashier for buying something worth 1 is invalid, because the cashier will give a change of 1 coin worth 100, which is equal to 100 coins of value 1.

Now, please help Darksun to calculate the minimum number of coins he will have after buying the GK.

Input

There are multiple cases. The first line of input is an integer T (T ≤ 10) which indicates the cases of test data.
For each test case, the first line contains an integer p (0 ≤ p ≤ 100000).
The second line contains 6 integers a, b, c, d, e, f (0 ≤ a, b, c, d, e, f ≤ 100).
It's confirmed that p <= a + b + c + d + e + f.

Output

For each case, please output one line, the minimum number of coins that Darksun has to carry when boarding the plane.

Sample Input

2
10
10 1 1 0 0 0
90
80 3 3 3 3 0

Sample Output

2
10

Author: ZHAO, Yueqi
Source: ZOJ Monthly, October 2015
Submit    Status