题目描述

现在有一个 $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}$。

你可以使用两种类型的操作，且每个操作只能使用一次，操作具体如下：

使用第 $i$ 个 $A$ 操作要花费 $a_i$ 枚金币。使用后：

• 将第 $i$ 行所有元素增加 $1$。即，将 $h_{i,1}, h_{i,2}, \ldots, h_{i,n}$ 都增加 $1$。

使用第 $j$ 个 $B$ 操作要花费 $b_j$ 枚金币。使用后：

• 将第 $j$ 列所有元素增加 $1$。即，将 $h_{1,j}, h_{2,j}, \ldots, h_{n,j}$ 都增加 $1$。

请计算使矩阵变得美丽所需的最少金币数，如果不可能实现则返回 $-1$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$。接下来是各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$——矩阵的大小。

接下来每个测试用例的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $h_{i,1}, h_{i,2}, \ldots, h_{i,n}$。

每个测试用例的下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$——操作 $A$ 的费用。

每个测试用例的下一行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$——操作 $B$ 的费用。

输出格式

对于每个测试用例，输出一个整数——所需的最少金币数，如果不可能则输出 $-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

样例 $\tt \#1$说明

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

对于第二个测试用例，我们可以使用第 $2$ 个和第 $4$ 个操作 $A$ ，以及第 $4$ 个操作 $B$：

• 初始状态：

  1 2 1 2
  3 2 1 2
  1 2 1 1
  1 3 1 2
  

• 使用第 $2$ 个操作 $A$ 后：

  1 2 1 2
  4 3 2 3
  1 2 1 1
  1 3 1 2
  

• 使用第 $4$ 个操作 $A$ 后：

  1 2 1 2
  4 3 2 3
  1 2 1 1
  2 4 2 3
  

• 使用第 $4$ 个操作 $B$ 后：

  1 2 1 3
  4 3 2 4
  1 2 1 2
  2 4 2 4
  

此时矩阵变得美丽，总费用为 $2 + 4 + 8 = 14$，这是可能的最小费用。

对于第三个测试用例，无论如何操作都无法使矩阵变得美丽，因此答案为 $-1$。

数据范围

• 对于 $30\%$ 的数据，保证所有测试用例的 $n$ 之和不超过 $10$。
• 对于 $100\%$ 的数据，保证 $1 \le t \le 100$， $1 \le h_{i, j}, a_i, b_j \le 10^9$ 且所有测试用例的 $n$ 之和不超过 $1000$。