Landing Platform

All submissions for this problem are available.
ISRO is planning to build a landing platform on MARS as a part of MOM. It has selected a small 2D rectangular region for the same, and every point in the region has a strength associated with it. The landing platform should be in the form of a cross (see definition below for more details) and as strong as possible.
The selected 2D rectangular region has M * N points represented by (x, y), for all 0 <= x < M, 0 <= y < N. Let W[i][j] denote the strength of the point (i, j). We define a cross as follows:

It consists of 2 line segments of equal length. The end points of the line segments should coincide with any of the given M * N points.

Each of the line segments are at an angle of 45° with both the X & Y axis.

Both the line segments intersect exactly at one point, and their centres coincide. (i.e) if the 2 line segments are represented by { (x_{11}, y_{11}), (x_{12}, y_{12}) }, { (x_{21}, y_{21}), (x_{22}, y_{22}) }, then (x_{11}+x_{12}) / 2 = (x_{21}+x_{22}) / 2 and (y_{11}+y_{12}) / 2 = (y_{21}+y_{22}) / 2. The point where the 2 line segments intersect is called the center of the cross.

Each line segment of the cross should have a nonzero length. Hence, a single point cannot be considered as a cross.
The strength of a cross is defined as the sum of strengths of all points that lie on it. Your task is to find the cross with maximum strength, which ISRO would like to use as the landing platform.
Input
The first line contains an integer T, denoting the number of test cases.
Then for each test case, the first line contains two integers M and N.
Each of the following M lines, contain N space separated integers, where the j^{th} integer on the i^{th} line denotes W[i1][j1], for all 1 <= i <= M, 1 <= j <= N.
Output
For each test case, output a single integer denoting the strength of the maximumstrength cross, on a separate line
Constraints
 T ≤ 100
 2 ≤ M ≤ 100
 2 ≤ N ≤ 100
 10^{6} ≤ W[i][j] ≤ 10^{6}
Example
Input: 2 3 3 1 1 1 1 1 1 1 1 1 2 3 0 1 2 2 3 1 Output: 1 6
Explanation
In the first case, the cross formed by the line segments {(0, 0), (2, 2)} and {(0, 2), (2, 0)} has the maximum strength = 1+(1)+1+(1)+(1) = 1. Note: You cannot choose a cross with 0 strength (not passing through any of the given points) here, because it is given that each line segment of the cross should pass through atleast one of the given points
In the second case, the cross formed by the line segments {(0, 0), (1, 1)} and {(0, 1), (1, 0)} has the maximum strength = 0+3+1+2 = 6
Author:  admin 
Tags  acmicpc, acmamr14, admin, enumeration, simple 
Date Added:  10102014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 