你是古贝尔兰一座城市的骄傲领袖。有 $$$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$$$。
示例
输入复制
421 22 1100 100100 10041 2 1 23 2 1 21 2 1 11 3 1 21 2 3 45 6 7 831 2 22 2 12 1 1100 100 100100 100 10068 7 2 8 4 87 7 9 7 1 18 3 1 1 8 56 8 3 1 1 41 4 5 1 9 67 1 1 6 8 211 23 20 79 30 1515 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$$$。