C. Удивительный город
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы гордый лидер города в Древней Берляндии. В городе расположено $$$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$$$ работников. Каждый работник может быть нанят не более одного раза.

Нанять работника $$$i$$$ в компании A стоит $$$a_i$$$ монет. После найма работник $$$i$$$:

  • Увеличит высоты всех зданий в строке $$$i$$$ на $$$1$$$. Другими словами, увеличит $$$h_{i, 1}, h_{i, 2}, \ldots, h_{i, n}$$$ на $$$1$$$.

Нанять работника $$$j$$$ в компании B стоит $$$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$$$) — размер таблицы.

$$$i$$$-я из следующих $$$n$$$ строк каждого набора содержит $$$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$$$.

Для второго набора мы можем нанять работника $$$2$$$ из компании A, работника $$$4$$$ из компании A и работника $$$4$$$ из компании B:

$$$1$$$$$$2$$$$$$1$$$$$$\color{red}2$$$$$$\implies$$$$$$1$$$$$$2$$$$$$1$$$$$$\color{red}3$$$
$$$\color{red}3$$$$$$\color{red}2$$$$$$\color{red}1$$$$$$\color{red}2$$$$$$\color{red}4$$$$$$\color{red}3$$$$$$\color{red}2$$$$$$\color{red}4$$$
$$$1$$$$$$2$$$$$$1$$$$$$\color{red}1$$$$$$1$$$$$$2$$$$$$1$$$$$$\color{red}2$$$
$$$\color{red}1$$$$$$\color{red}3$$$$$$\color{red}1$$$$$$\color{red}2$$$$$$\color{red}2$$$$$$\color{red}4$$$$$$\color{red}2$$$$$$\color{red}4$$$

Стоимость найма работников составляет $$$2 + 4 + 8 = 14$$$. Это минимально возможная стоимость.

Для третьего набора, независимо от того, что мы делаем, сделать город красивым невозможно. Таким образом, ответ равен $$$-1$$$.