Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID

Rikka with Coin

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 2176    Accepted Submission(s): 678

Problem Description
Rikka hates coins, and she used to never carry any coins with her. These days, Rikka is doing her summer internship abroad. Without mobile payment, Rikka has to face strange prices of commodities, and as a result of always using paper currency, she has to face mountainous coins on here table.

In the local currency system, there are $4$ kinds of coins: $10$ cents, $20$ cents, $50$ cents and $1$ dollar. Up to now, Rikka has gained at least $10^{100}$ coins for each kind.

Now, Rikka is going to have dinner in the canteen, and she decides to pay the bill only with coins. There are $n$ different combos in the canteen and the price of the $i$th is $w_i$ cents. Rikka would like to choose one combo as dinner but she has not decided to choose which one yet. Therefore, she wants to take some coins so that whichever she chooses, she can always pay the bill without receiving any change.

Since Rikka hates coins, she wants to carry as few coins as possible with her. As it is generally known that Rikka is not good at math, she wants you to help her make the decision.

The first line of the input contains a single integer $T(1 \leq T \leq 500)$, the number of test cases.

For each test case, the first line contains a single integer $n(1 \leq n \leq 100)$, the number of combos sold in the canteen.

The second line contains $n$ positive integers $w_1, \dots, w_n(1 \leq w_i \leq 10^9)$, which represents the prices.

For each test case, output a single line with a single integer which represents the minimum number of coins. If there is no valid solution, output $-1$.

In the first test case, one optimal solution is to bring one coin of $10$ cents and two coins of $20$ cents.

In the second test case, one optimal solution is to bring $5$ coins of one dollar.

Sample Input
3 5 10 20 30 40 50 5 100 200 300 400 500 1 1

Sample Output
3 5 -1


Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-07-14 09:34:10, Gzip enabled