Migrated from Lutece 2571 信道连接

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

2077 年，A 国和 B 国实现建交。为了保证两国通信正常，领导者在两国国内各建立了 $n$ 座基站并计划在两国基站间连接信道（即通信通道）以实现信号传输。A 国基站编号为 $a_1,a_2,\ldots ,a_n$，B 国基站编号为 $b_1,b_2,\ldots ,b_n$。由于地理位置的影响，基站 $a_i$ 仅可能向基站 $b_j\ (i\le j)$ 实现信道连接（同一国家内的基站不能相互连接，但一个基站可以与多个它国基站实现连接），且每个基站至少可以有一个可选择的连接对象，至多有四个可选择的连接对象。同时由于信号干扰的影响，A 国部分基站不能同时被使用（即部分 $a_i$ 不能同时有信道与其连接）。

领导者要求对于所有 B 国基站 $b_i$ 都有信道与其连接，且给定每个 A 国基站 $a_i$ 一个初始费用 $m_i$（$b_i$ 的费用可视为 $0$），若实际连接中对于基站 $a_i$ 共有 $d$ 条信道相连，则该基站的费用为 $m_i^d$（没有信道连接则该基站的费用为 $0$）。总花费定义为上述条件下所有 A 国基站的费用之和，请帮助两国找到满足上述要求的最少总花费。如果无法满足上述要求请输出 $-1$。

Input

第一行包含一个正整数 $t\ (1\le t\le 10)$，表示测试样例数。

每个样例的第一行包含一个正整数 $n\ (1\le n\le 18)$ ，表示两个国家各拥有的基站数量。

下面 $n$ 行表示两国基站间信道可连接情况的 $n\times n$ 的 $01$ 矩阵 $G$，$G_{i,j}$ 为 $1$，表示基站 $a_i$ 和 $b_j$ 可连接；$G_{i,j}$ 为 $0$，表示基站 $a_i$ 和 $b_j$ 不可连接。数据保证对于任意 $a_i$ 的度介于 $1$ 到 $4$ 之间，且当 $i>j$ 时，$G_{i,j}$ 一定为 $0$。

下面 $n$ 行表示 A 国基站间不可同时使用情况的 $n\times n$ 的 $01$ 矩阵 $A$，$A_{i,j}$ 为 $1$，表示基站 $a_i$ 和 $a_j$ 不可同时使用；$A_{i,j}$ 为 $0$，表示基站 $a_i$ 和 $a_j$ 可同时使用。数据保证 $A_{i,i}=0\ (1\le i\le n)$ 且 $A_{i,j}=A_{j,i}\ (1\le i,j\le n)$。

下面一行为以空格间隔的 $n$ 个整数，第 $i$ 个数表示基站 $a_i$ 对应的初始费用 $m_i\ (1\le m_i\le 100)$。

Output

输出共 $t$ 行，第 $i$ 行输出一个整数值表示第 $i$ 个样例对应的最小费用，或输出 $-1$ 表示无满足要求的情况。

Samples

2
4
1100
0110
0001
0001
0001
0001
0000
1100
3 4 4 5
4
1100
0110
0001
0001
0011
0001
1000
1100
3 4 4 5

17
-1

Note

第一个样例信道连接选择可以如下图所示：

Resources

2021 UESTC ICPC Training for Dynamic Programming