1994 - 迷宫探路
Description

给一个n \times n的迷宫,迷宫每一格有一个整数表示该点的难度值,求从(1,1)到(n,n)的所用路径中,难度差最小是多少。


Input

第一行一个数字n表示迷宫的长和宽

接下来n行n列的正方形数字,表示迷宫每个格子的难度值

Output

一个数值表示最小的难度值差

Examples

Input

3
1 2 3
1 2 3
1 1 1

Output

0
Hint

样例解释:

从(1,1)—>(2,1)—>(3,1)—>(3,2)—>(3,3) 这一路的难度值差为0


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 0
通过次数 0