在遥远的魔法大陆上，勇者艾尔接到了一项任务：探访一片神秘的浮空岛屿。浮空岛上分布着一个 N \times N 的格子，每个格子都拥有一个与众不同的魔力等级。为了完成任务，艾尔需要穿越这些格子，并且找到一种方法让他的旅程尽可能顺利。
艾尔每次从当前格子移动到相邻的格子（可以向东、南、西、北四个方向），都会感受到魔力波动的冲击，冲击强度取决于两个格子间的魔力等级差，数值为 D。因此，为了在两个格子之间自由穿梭，他必须拥有至少 D 点魔法护盾(魔法护盾不会被消耗，但是如果冲击超过 D 就会消失并受到伤害，则旅程失败)。
任务要求艾尔可以从任意位置出发，用最少的护盾强度穿越至少一半的格子（如果格子总数是奇数，那么一半的值向上取整）。
但是，这座浮空岛上魔力波动复杂，路径需要慎重选择。现在，艾尔请求你的帮助，计算出他如果可以从任意位置出发，最少需要多少魔法护盾强度，才能完成这一神秘的探访任务。
你能帮助勇者艾尔成功完成这次冒险吗？
第一行为一个整数 N。
第 2 到 N+1 行每行包含 N 个非负整数，表示当前格子的魔力等级。
输出一个整数，表示需要的护盾强度的最小值。
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
10 7 8 6 5 1 1 6 6 7 8 4 2 3 10 7 1 2 6 9 4 10 3 3 4 9 2 3 8 8 5 3 7 3 6 6 3 10 5 1 2 8 1 8 10 8 7 8 9 7 10 7 1 8 9 4 8 9 7 4 6 10 5 4 10 7 4 4 7 8 9 2 3 2 4 4 1 5 6 7 2 3 5 5 5 6 4 6 3 4 4 3 8 4 1 3 3 3 4 9 2
2
护盾强度只需要达到 3 就可以从 1,1 点出，发跑完图中 16 个格子，超过总格子数的一半。
当护盾强度为 2 时则无法满足。
| 测试点编号 | n |
|---|---|
| 测试点 1 \sim 2 | \le 10 |
| 测试点 3 \sim 6 | \le 100 |
| 测试点 7 \sim 10 | \le 500 |
每个格子的魔力等级 \leq 10^6 。