题目描述

有一块$\red{n *n }$的土地上，明明和亮亮站在$\red{(1,1)}$处。每块地上写有一个数字$\red{a(i, j)}$。现在他们决定玩一个游戏，每一秒钟，他们俩走向相邻且坐标变大的格子（从$\red{(x,y)}$到$\red{(x+1,y)}$或者从$\red{(x,y)}$到$\red{(x,y+1)）}$，他们俩可以按照不同方式来走，最后经过$\red{2n-1}$步到达$\red{(n,n)}$处。明明和亮亮每一秒钟计算他们站的两个位置上数字的差的绝对值，他们希望这些差值的和最大，请问这个最大的和是多少？

输入格式

第一行一个正整数$\red{n}$。 后面$\red{n}$行，每行$\red{n}$个整数，分别表示每块地上的数字。

输出格式

一个整数，表示最大的差值的和。

样例

输入样例

4
1 2 3 4
1 5 3 2
8 1 3 4
3 2 1 5

输出样例

提示

$\red{n <= 100, }$每块地上的数字的绝对值不超过$\red{300}$。