题目描述

小明有一片高低起伏的农田，可以用一个 $N \times N$ 的网格来描述，每个格子上有一个非负整数表示海拔高度（$1 \leq N \leq 500$）。

小明想买一辆拖拉机在农田里行驶。拖拉机从一个格子移动到相邻格子（上、下、左、右之一）时，如果两地海拔差为 $D$，则需要花费 $D$ 个单位的通行费。

小明希望支付足够的通行费，使得拖拉机从某个格子出发，能够成功行驶到至少一半的格子（如果总格子数为奇数，则至少行驶到 $\lceil N^2 / 2 \rceil$ 个格子）。请帮他计算最少需要多少通行费。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行 $N$ 个空格分隔的非负整数（每个不超过 $10^6$），表示农田各格子的海拔。

输出格式

一个整数，表示满足条件的最小通行费。

样例

5 
0 0 0 3 3 
0 0 0 0 3 
0 9 9 3 3 
9 9 9 3 3 
9 9 9 9 3

3