题目描述

Ark得到了一只闪电兵（若不知其为何物可以申请向周围玩过星际的同学请教），准备用它来处理一块n*n(n<=5)的矩阵上的小狗(若不知其为何物可以申请向周围玩过星际的同学请教)。它比较神奇可以选择某个大小不限矩形(可能是长方形)上释放闪电。每在一块格子释放闪电会消耗1的mp，但能得kill掉这一格的所有小狗。问Ark能获得的最大收益。（注：释放闪电的一定是一个矩形，当然也可能选择不释放，这个时候收益为0。不存在某些格子在所选矩形中而不被释放的情况。最大收益为总kill数-总mp消耗）

输入格式

第一行一个整数n表示整个矩形场地的大小。

接下来给出n*n个整数

第i行第j个表示该格子上的小狗数量。

输出格式

一个整数p表示最大利润。

样例 #1

样例输入 #1

3
0 0 0
0 10 0
0 0 2

样例输出 #1

9

提示

获利依次为: 8 9 8