题目描述

给定一个 n 行 n 列的矩阵，第 i 行第 j 列为 numij。大 S 和小 S 从第一行第一列出发，每次向正右方走一格或向正下方走一格，不可走出矩阵，最终到达右下角位置。两人经过的数字可以不相同，设大 S 的路径为起点 →a1→a2→a3→……→a2n-3→终点，小 S 的路径为起点 →b1→b2→b3→……→b2n-3→ 终点。大小 S 想知道 |a1-b1|+|a2-b2|+…+|a2n-3-b2n-3| 的值最大可以是多少。

输入格式

第一行一个正整数n。

后面n行，每行n个整数，描述这个矩阵。

输出格式

一个整数，见题面描述。

样例输入

4

1 2 3 4

1 5 3 2

8 1 3 4

3 2 1 5

样例输出

13