MINES4  Four Mines
A Company that Makes Everything (ACME) has entered the surface mining business. They bought a rectangular field which is split into cells, with each cell having a profit value. A mine is a nonempty rectangular region, and the profit of a mine is equal to the sum of the values of all its cells. ACME wants to extract ore from four different nonoverlapping mines. You are to choose these mines to maximize the total profit.
Input
The first line contains an integer T (1 ≤ T ≤ 5), denoting the number of test cases.
For each test case, the first line contains two positive integers R and C (2 ≤ R,C ≤ 100), denoting the number of rows and columns of a rectangular field.
Each of next R lines contain C integers between 10000 and 10000, denoting a profit value for each cell in that row.
Output
For each test case, print a number on its own line, denoting the maximum total profit that can be extracted from four mines.
Example
Input: 2 5 5 10 10 1 1 10 10 1 1 1 10 1 1 1 1 1 1 1 1 10 10 10 1 1 10 10 2 3 1 2 3 4 5 66 Output: 99 60
hide comments
Leopard1:
20120518 05:17:54
n^4 is not too slow for the problem. 

:D:
20111102 14:12:32
You must take into account that SPOJ is relatively slow. You may want to test the speed on the site itself. Find a problem with a very big time limit (for example XC) hardcode the input data into code and ignore input stream. Then see how much time it will take to execute and give WA for example. There is also and Ideone.com system, running on the same engine, but that seems to be much faster than SPOJ. 

pulkit:
20110629 14:39:22
Can you check submission ID 5313130

Added by:  Luka Kalinovcic 
Date:  20091122 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  ThreeMines from TopCoder SRM 315 extended 