CF2096C Wonderful City

你是古伯兰王国一座城市的骄傲领导者。这座城市有 $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$ 行所有建筑的高度增加 $1$。即，将 $h_{i,1}, h_{i,2}, \ldots, h_{i,n}$ 都增加 $1$。 雇佣 B 公司的第 $j$ 名工人需要花费 $b_j$ 枚金币。雇佣后，该工人会： - 将第 $j$ 列所有建筑的高度增加 $1$。即，将 $h_{1,j}, h_{2,j}, \ldots, h_{n,j}$ 都增加 $1$。 请计算使城市变得美丽所需的最少金币数，如果不可能实现则返回 $-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$。

对于第一个测试用例，可以看到城市已经是美丽的，因此答案为 $0$。 对于第二个测试用例，我们可以雇佣 A 公司的第 $2$ 名工人、A 公司的第 $4$ 名工人和 B 公司的第 $4$ 名工人： - 初始状态： ``` 1 2 1 2 3 2 1 2 1 2 1 1 1 3 1 2 ``` - 雇佣 A 公司第 $2$ 名工人后： ``` 1 2 1 2 4 3 2 3 1 2 1 1 1 3 1 2 ``` - 雇佣 A 公司第 $4$ 名工人后： ``` 1 2 1 2 4 3 2 3 1 2 1 1 2 4 2 3 ``` - 雇佣 B 公司第 $4$ 名工人后： ``` 1 2 1 3 4 3 2 4 1 2 1 2 2 4 2 4 ``` 此时城市变得美丽，雇佣工人的总费用为 $2 + 4 + 8 = 14$，这是可能的最小费用。 对于第三个测试用例，无论如何操作都无法使城市变得美丽，因此答案为 $-1$。 翻译由 DeepSeek V3 完成