题目描述

有一张 $N \times N$ 的方格地图，每个格子都有一个魔力值。勇者可以选择任意一个格子作为起点，每次可以移动到与当前格子上、下、左、右相邻的格子。

勇者的护盾强度为 $D$。只有当两个相邻格子的魔力值之差的绝对值不超过 $D$ 时，勇者才能在这两个格子之间移动。护盾在移动过程中不会被消耗。

勇者需要从所选起点出发，到达至少 $\left\lceil\dfrac{N^2}{2}\right\rceil$ 个不同的格子。请计算满足要求的最小护盾强度。

输入格式

第一行包含一个正整数 $N$，表示地图的边长。

接下来 $N$ 行，每行包含 $N$ 个非负整数。第 $i$ 行第 $j$ 个整数 $a_{i,j}$ 表示第 $i$ 行第 $j$ 列格子的魔力值。

输出格式

输出一个整数，表示满足要求的最小护盾强度。

5
1 1 1 4 4
1 1 1 1 4
1 9 9 4 4
9 9 9 4 4
9 9 9 9 4

3

4
3 2 1 0
2 3 4 5
1 2 3 4
3 4 5 6

1

数据范围与提示

• $1 \le N \le 500$
• $0 \le a_{i,j} \le 10^6$