题目描述

$\red{FJ}$有块农田太崎岖了，他要买一辆新拖拉机才能在这里巡视。这块农田由$\red{N \times\ N}$个格子的非负整数表示高度$\red{(1<=N<=500)}$。拖拉机从当前格子走到相邻格子（东、南、西、北四个方向）的代 价为高度差$\red{D，}$则$\red{FJ}$驶过这两个格子的拖拉机最少也要值$\red{D}$块钱。

$\red{FJ}$愿意花足够的钱买一辆新的拖拉机使得他能以最小的高度差走遍所有格子的一半$\red{(}$如果格子总数是奇数，那么一半的值为四舍五入的值$\red{)}$。因为$\red{FJ}$很懒，所以他找到你帮他编程计 算他最小需要花多少钱买到符合这些要求的拖拉机。

输入输出格式

输入格式

第一行为一个整数$\red{N}$

第$\red{2}$到$\red{N+1}$行每行包含$\red{N}$个非负整数（不超过$\red{1,000,000）}$，表示当前格子的高度。

输出格式

共一行，表示$\red{FJ}$买拖拉机要花的最小价钱。

样例

输入样例

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