该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

小 A 有一片农场区域，大小为 N*N (1 <= N <= 500)，这 N*N 个格子中，有些为山 丘，高度都为正整数，有些是平地，高度为 0。小 A 从当前格子走到相邻格子（东、南、西、 北四个方向）的代价为高度差。求小 A 以最小的高度差能走遍所有格子的一半。（如果格子 总数为奇数，则一半的值为四舍五入的值）。

Format

Input

第一行为一个整数 N； 以下 N 行，每行为 N 个空格分隔开的整数（0..1,000,000）。

Output

求遍历一半格子的最小代价。

Samples

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

Limitation

高度差为 3。 20%的数据，1 <= N <= 10 40%的数据，1 <= N <= 50 60%的数据，1 <= N <= 100 100%的数据，1 <= N <= 500