你是古代伯兰一座城市的骄傲领导者。城市中有 $n^2$ 座建筑，排列成一个 $n$ 行 $n$ 列的网格。位于第 $i$ 行第 $j$ 列的建筑的高度为 $h_{i, j}$。

如果任意两座边相邻的建筑高度都不相同，则这座城市是美丽的。换句话说，必须满足以下条件：

• 不存在位置 $(i, j)$ ($1 \leq i \leq n$, $1 \leq j \leq n - 1$) 使得 $h_{i, j} = h_{i, j + 1}$。
• 不存在位置 $(i, j)$ ($1 \leq i \leq n - 1$, $1 \leq j \leq n$) 使得 $h_{i, j} = h_{i + 1, j}$。

A 公司有 $n$ 名工人，B 公司有 $n$ 名工人。每名工人最多只能被雇佣一次。

雇佣 A 公司的工人 $i$ 需要花费 $a_i$ 个硬币。雇佣后，工人 $i$ 会：

• 将第 $i$ 行所有建筑的高度增加 $1$。即将 $h_{i, 1}, h_{i, 2}, \ldots, h_{i, n}$ 增加 $1$。

雇佣 B 公司的工人 $j$ 需要花费 $b_j$ 个硬币。雇佣后，工人 $j$ 会：

• 将第 $j$ 列所有建筑的高度增加 $1$。即将 $h_{1, j}, h_{2, j}, \ldots, h_{n, j}$ 增加 $1$。

请找出使城市变得美丽所需的最小硬币数，如果不可能则报告不可能。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 100$)。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 1000$) — 网格的大小。

每个测试用例接下来的 $n$ 行中的第 $i$ 行包含 $n$ 个整数 $h_{i, 1}, h_{i, 2}, \ldots, h_{i, n}$ ($1 \le h_{i, j} \le 10^9$) — 第 $i$ 行建筑的高度。

每个测试用例的下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — 雇佣 A 公司工人的花费。

每个测试用例的最后一行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ($1 \le b_j \le 10^9$) — 雇佣 B 公司工人的花费。

保证所有测试用例的 $n$ 之和不超过 $1000$。

输出

对于每个测试用例，输出一个整数 — 所需的最小硬币数，如果不可能则输出 $-1$。

4
2
1 2
2 1
100 100
100 100
4
1 2 1 2
3 2 1 2
1 2 1 1
1 3 1 2
1 2 3 4
5 6 7 8
3
1 2 2
2 2 1
2 1 1
100 100 100
100 100 100
6
8 7 2 8 4 8
7 7 9 7 1 1
8 3 1 1 8 5
6 8 3 1 1 4
1 4 5 1 9 6
7 1 1 6 8 2
11 23 20 79 30 15
15 83 73 57 34 63

0
14
-1
183

样例解释

对于第一个测试用例，我们可以看到城市已经是美丽的。因此答案为 $0$。

对于第二个测试用例，我们可以雇佣 A 公司的工人 $2$、A 公司的工人 $4$ 以及 B 公司的工人 $4$：

雇佣工人的花费为 $2 + 4 + 8 = 14$。这是可能的最小花费。

对于第三个测试用例，无论我们怎么做，都不可能使城市变得美丽。因此答案为 $-1$。