G. Миллиард оттенков серого
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы должны покрасить оттенками серого плитки стены размера $$$n\times n$$$. Стена состоит из $$$n$$$ рядов плиток, в каждом по $$$n$$$ плиток.

Плитки на границе стены (т.е. в первом ряду, последнем ряду, первом столбце и последнем столбце) уже покрашены, и вы не должны менять их цвет. Все остальные плитки не покрашены.

Некоторые из плиток сломаны, их нельзя красить. Гарантируется, что плитки на границе не сломаны.

Вы должны покрасить все не сломанные плитки, которые еще не покрашены. Когда вы красите плитку, вы можете выбрать один из $$$10^9$$$ оттенков серого, пронумерованных от $$$1$$$ до $$$10^9$$$. Вы можете покрасить несколько плиток одним и тем же оттенком. Формально, раскраска стены эквивалентна присвоению оттенка (целое число от $$$1$$$ до $$$10^9$$$) каждой неокрашенной плитке, которая еще не закрашена.

Контраст между двумя плитками равен модулю разности между оттенками двух плиток. Общий контраст стены является суммой контрастов по всем парам соседних несломанных плиток (две плитки соседние, если они имеют общую сторону).

Вычислите минимально возможный суммарный контраст стены.

Входные данные

Первая строка содержит $$$n$$$ ($$$3\le n\le 200$$$)  — количество строк и столбцов.

Затем следуют $$$n$$$ строк, каждая из которых содержит $$$n$$$ целых чисел. $$$i$$$-я из этих строк описывает $$$i$$$-ю строку плиток. Она содержит $$$n$$$ целых чисел $$$a_{ij}$$$ ($$$-1\le a_{ij} \le 10^9)$$$. Значение $$$a_{ij}$$$ описывает плитку в $$$i$$$-й строке и $$$j$$$-м столбце:

  • Если $$$a_{ij}=0$$$, то плитка не покрашена и будет покрашена.
  • Если $$$a_{ij}=-1$$$, то плитка сломана и не должна быть покрашена.
  • Если $$$1\le a_{ij}\le 10^9$$$, то плитка уже закрашена оттенком $$$a_{ij}$$$.
Гарантируется, что плитки на границе уже покрашены, плитки не на границе еще не покрашены, и плитки на границе не сломаны.
Выходные данные

Выведите единственное целое число  — минимально возможный суммарный контраст стены.

Примеры
Входные данные
3
1 7 6
4 0 6
1 1 1
Выходные данные
26
Входные данные
3
10 100 1
1 -1 100
10 10 10
Выходные данные
396
Входные данные
5
6 6 5 4 4
6 0 0 0 4
7 0 0 0 3
8 0 0 0 2
8 8 1 2 2
Выходные данные
34
Входные данные
7
315055237 841510063 581663979 148389224 405375301 243686840 882512379
683199716 -1 -1 0 0 0 346177625
496442279 0 0 0 0 0 815993623
223938231 0 0 -1 0 0 16170511
44132173 0 -1 0 0 0 130735659
212201259 0 0 -1 0 0 166102576
123213235 506794677 467013743 410119347 791447348 80193382 142887538
Выходные данные
10129482893
Примечание

Пояснение первого примера: Первоначальная конфигурация плиток (плитки, которые нужно покрасить, обозначаются ?): 


1 7 6
4 ? 6
1 1 1
Возможный способ покраски плитки, достигающий минимально возможного суммарного контраста в $$$26$$$: 

1 7 6
4 5 6
1 1 1

Пояснение второго примера: Так как все плитки либо покрашены, либо сломаны, делать нечего. Общий контраст составляет $$$396$$$.

Пояснение третьего примера: Первоначальная конфигурация плиток (плитки, которые нужно покрасить, обозначены ?): 


6 6 5 4 4
6 ? ? ? 4
7 ? ? ? 3
8 ? ? ? 2
8 8 1 2 2
Возможный способ покраски плитки достигает минимально возможного контраста в $$$34$$$: 

6 6 5 4 4
6 6 5 4 4
7 7 5 3 3
8 8 2 2 2
8 8 1 2 2