题目描述

给定一个N×N的整数矩阵，选取若干连续行和连续列，它们的交集构成一个子矩阵。

请找出元素之和最大的非空子矩阵，输出其元素之和。子矩阵至少包含一个格子。

输入格式

第一行整数N。接下来N行，每行N个整数。

输出格式

输出非空子矩阵的最大元素和。

样例

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

15

数据范围

1≤N≤100；矩阵元素在-127至127之间。