## 【19HDU多校】Rikka with Coin，贪心

### 传送门

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5] = {10, 20, 20, 20, 50};
int b[10], n;
ll d[210];
set<int> st[1 << 6];
void dfs(set<int> &t, int now, int sum)
{
t.insert(sum);
//if(now > n) return;
while(now < n)
{
++now;
dfs(t, now, sum + b[now]);
}
}
int main()
{
freopen("02.in", "r", stdin);
for(int i = 1; i < 1 << 5; i++)
{
n = 0;
for(int j = 0; j < 5; j++)
{
if(1 & (i >> j)) b[n++] = a[j];
}
n--;
for(int j = 0; j <= n; j++) dfs(st[i], j, b[j]);
}

// for(int i = 1; i < 1 << 5; i++)
// {
//     cout << i << ':';
//     for(auto it = st[i].begin(); it != st[i].end(); it++) cout << *it << ' ';
//     cout << endl;
// }
int T; cin >> T;
while(T--)
{
int num; scanf("%d", &num);
int flag = 0;
for(int i = 1; i <= num; i++)
{
scanf("%lld", &d[i]);
if(d[i] % 10) flag = 1;
}
//sort(d + 1, d + 1 + num);
if(flag)
{
printf("-1\n");
continue;
}
ll ans = 1e12;
for(int i = 0; i < 1 << 5; i++)
{
if(i == 23)
{
int debug = 1;
}
int cz = __builtin_popcount(i);
ll dol = 0;
int can = 1;
for(int j = 1; j <= num; j++)
{
if(d[j] >= 100)
{
int tmp = d[j] % 100;
tmp += 100;
if(st[i].find(tmp) != st[i].end())
{
dol = max((d[j] - tmp) / 100, dol);
continue;
}
}
if(st[i].find(d[j] % 100) != st[i].end()) dol = max(d[j] / 100, dol);
else if(d[j] % 100 == 0) dol = max(d[j] / 100, dol);
else can = 0;
}
if(can == 0) continue;
//ans = min(ans, dol + cz);
if(ans > dol + cz) ans = dol + cz;
}
cout << ans << endl;
}
}
//23:10 20 30 40 50 60 70 80 90 100

// 110 70 190
// 1010 90 110