← 返回题目列表

Codeforces · 2096/C

C. 美妙的城市

中文机器翻译题面 查看原题

你是古贝尔兰一座城市的骄傲领袖。有 $$$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$$$) — 行中建筑物的高度$$$我$$$。

每个测试用例的下一行包含 $$$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$$$ 工人:

$$$1$$$$$$2$$$$$$1$$$$$$\颜色{红色}2$$$$$$\ 意味着 $$$$$$1$$$$$$2$$$$$$1$$$$$$\颜色{红色}3$$$
$$$\颜色{红色}3$$$$$$\颜色{红色}2$$$$$$\颜色{红色}1$$$$$$\颜色{红色}2$$$$$$\颜色{红色}4$$$$$$\颜色{红色}3$$$$$$\颜色{红色}2$$$$$$\颜色{红色}4$$$
$$$1$$$$$$2$$$$$$1$$$$$$\颜色{红色}1$$$$$$1$$$$$$2$$$$$$1$$$$$$\颜色{红色}2$$$
$$$\颜色{红色}1$$$$$$\颜色{红色}3$$$$$$\颜色{红色}1$$$$$$\颜色{红色}2$$$$$$\颜色{红色}2$$$$$$\颜色{红色}4$$$$$$\颜色{红色}2$$$$$$\颜色{红色}4$$$

雇用工人的成本为 $$$2 + 4 + 8 = 14$$$。这是可能的最低成本。

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