Agent 47 - LightOJ

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 15;
int dp[1 << N], n, b[N];
char a[N][N];
void read()
{
    cin >> n;
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 0; i < n; ++ i)
    {
        cin >> b[i];
    }
    for (int i = 0; i < n; ++ i)
    {
        for (int j = 0; j < n; ++ j)
        {
            cin >> a[i][j];
        }
    }
}
int Ceil(int u, int v)
{
    return (u + v - 1)/v;
}
void solve()
{
    for (int mask = 0; mask < (1 << n); ++ mask)
    {
        for (int j = 0; j < n; ++ j)
        {
            if ((mask & (1 << j)) == 0)
            {
                int damage = 1;
                for (int k = 0; k < n; ++ k)
                {
                    if (mask & (1 << k))
                    {
                        damage = max(damage, a[k][j] - '0');
                    }
                }
                dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + Ceil(b[j], damage));
            }
        }
    }
    cout << dp[(1 << n) - 1] << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen(TASK".INP", "r", stdin);
    //freopen(TASK".OUT", "w", stdout);
    int t = 1;
    bool typetest = true;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        cout << "Case " << __ << ": ";
        read();
        solve();
    }
}