你必须用灰色阴影来绘制 $$$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}$$$。
输出
打印一个整数——墙壁的最小可能总对比度。
示例
输入 #1
3 1 7 6 4 0 6 1 1 1
输出 #1
26
输入 #2
3 10 100 1 1 -1 100 10 10 10
输出 #2
396
输入 #3
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
输出 #3
34
输入#4
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
输出#4
10129482893
注意
第一个测试用例的说明:图块的初始配置是(要绘制的图块用?表示):
1 7 64 ? 61 1 1
1 7 64 5 61 1 1
第二个测试用例的解释:由于所有瓷砖要么被涂漆,要么被破坏,所以没有什么可做的。总对比度为$$$396$$$。
第三个测试用例的说明:图块的初始配置是(要绘制的图块用?表示):
6 6 5 4 46 ? ? ? 47 ? ? ? 38 ? ? ? 28 8 1 2 2
6 6 5 4 46 6 5 4 47 7 5 3 38 8 2 2 28 8 1 2 2