QUESTION :
Question ID : ACM14AM4
ISRO is planning to build a landing platform on MARS as a part of MOM. It has selected a small 2-D 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 2-D 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 { (x11, y11), (x12, y12) }, { (x21, y21), (x22, y22) }, then (x11+x12) / 2 = (x21+x22) / 2 and (y11+y12) / 2 = (y21+y22) / 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 non-zero 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 jth integer on the ith line denotes W[i-1][j-1], for all 1 <= i <= M, 1 <= j <= N.
Output
For each test case, output a single integer denoting the strength of the maximum-strength cross, on a separate line
Constraints
T ≤ 100
2 ≤ M ≤ 100
2 ≤ N ≤ 100
-106 ≤ W[i][j] ≤ 106
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
SOLUTION :
Solution ID :8466199
this code is giving wrong answer.
in g++ it is working good for all cases i thoghthmay be possible.
how can i correct it.
