All Submissions


You are given a circular (both horizontally and vertically) square of size NxN. Find the maximum sub-rectangle sum.

Input Specifications
Input consists of a number of test cases. Read till EOF.
First line of each test case consists of a single integer N. N lines follow with N integers (aij) in each of them giving the values contained in the circular square.

Output Specifications
Print maximum sub-rectangle sum for each test case in a separate line where the sub-rectangle should contain at least one element.

Constraints
No. of test cases < 20
1 <= N <= 75
-100 <= aij <= 100

Sample Cases
Input
5
0 -4 1 -1 0
-3 2 2 3 -2
-3 0 4 1 -1
-3 2 3 -2 1
-3 -4 -3 2 4
5
1 -1 0 0 -4
2 3 -2 -3 2
4 1 -1 -3 0
3 -2 1 -3 2
-3 2 4 -3 -4
5
4 1 -1 -3 0
3 -2 1 -3 2
-3 2 4 -3 -4
1 -1 0 0 -4
2 3 -2 -3 2


Output
15
15
15


Explanation

Problem Setter : Shikhar Sharad

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 6 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0