| Hello 2022 |
|---|
| Закончено |
Циклическая страна представляет клетчатое поле $$$2n \times 2n$$$. Строки этого поля пронумерованы числами от $$$1$$$ до $$$2n$$$ сверху вниз, а столбцы пронумерованы числами от $$$1$$$ до $$$2n$$$ слева направо. Клетка $$$(x, y)$$$ — это клетка на пересечении строки $$$x$$$ и столбца $$$y$$$ для $$$1 \leq x \leq 2n$$$ и $$$1 \leq y \leq 2n$$$.
Сейчас Ваши $$$n^2$$$ друзей находятся в левом верхнем углу этого поля. Иными словами, в каждой клетке $$$(x, y)$$$, где $$$1 \leq x, y \leq n$$$ находится ровно один Ваш друг. В некоторых из остальных клеток поля находятся сугробы.
Ваши друзья хотят переместиться в правый нижний угол этого поля. Для этого в каждой клетке $$$(x, y)$$$, для которой $$$n+1 \leq x, y \leq 2n$$$ должен оказаться ровно один друг. При этом неважно, в какой клетке окажется каждый друг.
Вы решили помочь своим друзьям совершить поход.
Вы будете давать друзьям инструкции по перемещению одного из следующих видов:
- Выбрать некоторую строку $$$x$$$. Все друзья, находящиеся в этой строке перемещаются в следующую клетку этой строки. После этой операции друг из клетки $$$(x, y)$$$ окажется в клетке $$$(x, y + 1)$$$ для $$$1 \leq y < 2n$$$, a друг из клетки $$$(x, 2n)$$$ окажется в клетке $$$(x, 1)$$$.
- Выбрать некоторую строку $$$x$$$. Все друзья, находящиеся в этой строке перемещаются в предыдущую клетку этой строки. После этой операции друг из клетки $$$(x, y)$$$ окажется в клетке $$$(x, y - 1)$$$ для $$$1 < y \leq 2n$$$, а друг из клетки $$$(x, 1)$$$ окажется в клетке $$$(x, 2n)$$$.
- Выбрать некоторый столбец $$$y$$$. Все друзья, находящиеся в этом столбце перемещаются в следующую клетку этого столбца. После этой операции друг из клетки $$$(x, y)$$$ окажется в клетке $$$(x + 1, y)$$$ для $$$1 \leq x < 2n$$$, а друг из клетки $$$(2n, y)$$$ окажется в клетке $$$(1, y)$$$.
- Выбрать некоторый столбец $$$y$$$. Все друзья, находящиеся в этом столбце перемещаются в предыдущую клетку этого столбца. После этой операции друг из клетки $$$(x, y)$$$ окажется в клетке $$$(x - 1, y)$$$ для $$$1 < x \leq 2n$$$, а друг из клетки $$$(1, y)$$$ окажется в клетке $$$(2n, y)$$$.
Обратите внимание, как ведут себя друзья, находящиеся на границах клетчатого поля в этих инструкциях.
Пример применения третьей операции ко второму столбцу. Здесь разноцветные кружки обозначают Ваших друзей, а синим покрашены клетки с сугробами. Вы можете давать инструкции любое количество раз. Вы можете давать инструкции разных видов. Если после одной из этих инструкций один из друзей окажется в сугробе, то он замёрзнет.
Чтобы друзья не замёрзли, Вы можете до объявления первой инструкции убрать некоторые сугробы с помощью следующей операции:
- Выбрать клетку $$$(x, y)$$$, в которой сейчас находится сугроб и убрать его за $$$c_{x, y}$$$ монет.
Вы можете делать эту операцию любое количество раз.
Вы хотите потратить как можно меньше монет на уборку сугробов, а затем дать друзьям инструкции таким образом, чтобы они переместились в правый нижний угол поля и никто из них не замёрз.
Определите, сколько монет Вы потратите.
В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следуют описания этих наборов.
В первой строке дано одно число $$$n$$$ ($$$1 \leq n \leq 250$$$) — половина длины стороны поля.
В следующих $$$2n$$$ строках дано по $$$2n$$$ чисел $$$c_{i, 1}, c_{i, 2}, \ldots, c_{i, 2n}$$$ ($$$0 \leq c_{i, j} \leq 10^9$$$) — стоимости уборки сугробов в каждой клетке. Если $$$c_{i, j} = 0$$$ для некоторых $$$i, j$$$, то в клетке $$$(i, j)$$$ нет сугроба. Иначе в клетке $$$(i, j)$$$ есть сугроб.
Гарантируется, что $$$c_{i, j} = 0$$$ для $$$1 \leq i, j \leq n$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$250$$$.
Для каждого набора входных данных выведите одно число — минимальное количество монет, которое Вам нужно потратить.
410 81 9920 0 0 00 0 0 09 9 2 29 9 9 920 0 4 20 0 2 44 2 4 22 4 2 440 0 0 0 0 0 0 20 0 0 0 0 0 2 00 0 0 0 0 2 0 00 0 0 0 2 0 0 00 0 0 2 2 0 2 20 0 2 0 1 6 2 10 2 0 0 2 4 7 42 0 0 0 2 0 1 6
100 22 14 42
В первом наборе входных данных можно убрать сугробы в клетках $$$(2, 1)$$$ и $$$(2, 2)$$$ за $$$100$$$ монет. После этого Вы можете дать инструкции
- Перемещение в предыдущую клетку в первом столбце. После этого друг окажется в клетке $$$(2, 1)$$$.
- Перемещение в следующую клетку во второй строке. После этого друг окажется в клетке $$$(2, 2)$$$ и закончит поход.
Во втором наборе входных данных можно убрать все сугробы на клетках столбцов $$$3$$$ и $$$4$$$ за $$$22$$$ монеты. После этого Вы можете дать инструкции
- Перемещение в следующую клетку в первой строке.
- Перемещение в следующую клетку в первой строке.
- Перемещение в следующую клетку во второй строке.
- Перемещение в следующую клетку во второй строке.
- Перемещение в следующую клетку в третьем столбце.
- Перемещение в следующую клетку в третьем столбце.
- Перемещение в следующую клетку в четвёртом столбце.
- Перемещение в следующую клетку в четвёртом столбце.
Можно показать, что в результате этих инструкций ни один из друзей не замёрзнет, и что нельзя убрать сугробы меньшей суммарной стоимости.
