Циклическая страна представляет клетчатое поле \(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}\) монет.
Вы можете делать эту операцию любое количество раз.
Вы хотите потратить как можно меньше монет на уборку сугробов, а затем дать друзьям инструкции таким образом, чтобы они переместились в правый нижний угол поля и никто из них не замёрз.
Определите, сколько монет Вы потратите.
Примечание
В первом наборе входных данных можно убрать сугробы в клетках \((2, 1)\) и \((2, 2)\) за \(100\) монет. После этого Вы можете дать инструкции
- Перемещение в предыдущую клетку в первом столбце. После этого друг окажется в клетке \((2, 1)\).
- Перемещение в следующую клетку во второй строке. После этого друг окажется в клетке \((2, 2)\) и закончит поход.
Во втором наборе входных данных можно убрать все сугробы на клетках столбцов \(3\) и \(4\) за \(22\) монеты. После этого Вы можете дать инструкции
- Перемещение в следующую клетку в первой строке.
- Перемещение в следующую клетку в первой строке.
- Перемещение в следующую клетку во второй строке.
- Перемещение в следующую клетку во второй строке.
- Перемещение в следующую клетку в третьем столбце.
- Перемещение в следующую клетку в третьем столбце.
- Перемещение в следующую клетку в четвёртом столбце.
- Перемещение в следующую клетку в четвёртом столбце.
Можно показать, что в результате этих инструкций ни один из друзей не замёрзнет, и что нельзя убрать сугробы меньшей суммарной стоимости.