Maximum Submatrix

Problem Background

Special for beginners, ^_^

Problem Description

The size of a matrix is defined as the sum of all its elements.

Given a matrix, your task is to find the largest non-empty (of size at least $1\times 1$) submatrix. For example, in the following $4\times 4$ matrix

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

the maximum submatrix is

 9  2
-4  1
-1  8

whose size is $15$.

Input Format

The input is an $N\times N$ matrix.

The first line gives $N\;(0 < N \le 100)$. In the following lines, in order (first the $N$ integers of the first row from left to right, then the $N$ integers of the second row from left to right, and so on), the $N^2$ integers of the matrix are given, separated by whitespace (spaces or blank lines). It is known that all integers in the matrix are in the range $[-127, 127]$.

Output Format

Output the size of the maximum submatrix.

Sample Input

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

Sample Output

15

Constraints

1s, 1024KiB for each test case.