Matrix Sum
Time Limit: 1.0 s
Memory Limit: 256.0 MB
Description
You are given a N x M matrix where N represent number of rows and M represent number of coloums. You need to rearrange this matrix such way that, two consecutive cell (it could be row or coloum) sum is maximize overall.
if N = 2 and M = 2, then N * M matrix should be like this:
All possible consecutive cell sum marked in red colour.
(5,3) = 5 + (3) = 2
(5,2) = 5 + 2 = 7
(2,6) = 2 + 6 = 8
(3,6) = 3 + 6 = 3.
So overall maximize sum is 2. (lowest sum in the matrix).
You need to rearrange matrix value such way that maximize sum is as maximum as possible.
Note : Two consecutive cell, not full coloum or row.
Input
First Line T, Number of test cases.
In each test case,
First line N and M, number of row and coloum, respectively.
Second line a matrix A[][] and the length of the matrix is \(N * M\).
\(1<=T<=10^3\)
\(1<=N,M<=500\) , \(N * M > 1\)
\(10^3 <= A[][]<= 10^3\)
It is guranteed that sum of \(N * M\) over all test case does not exceed \(3 * 10^5\) .
Output
In each test case, print the maximize sum after rearrange the matrix.
Sample
Input  Output 



Information
 ID
 1065
 Difficulty
 9
 Category
 Implementation  Data_Structure Click to Show
 Tags
 (None)
 # Submissions
 24
 Accepted
 2
 Accepted Ratio
 8%
 Uploaded By
Related
In following contests: