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 non-empty 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 non-overlapping mines. You are to choose these mines to maximize the total profit.

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 non-empty 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 <b>four</b> different non-overlapping mines. You are to choose these mines to maximize theA 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 non-empty 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 <b>four</b> different non-overlapping mines. You are to choose these mines to maximize the total profit. 
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 non-empty 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 <b>four</b> different non-overlapping mines. You are to choose these mines to maximize the total profit. 
 total profitA 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 non-empty 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 non-overlapping mines. You are to choose these mines to maximize the total profit.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 non-empty 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 <b>four</b> different non-overlapping 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

Added by:Luka Kalinovcic
Date:2009-11-22
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

hide comments
2019-09-27 01:36:41
Is it dp?

Last edit: 2019-09-27 02:34:01
2012-05-18 05:17:54 Leopard1
n^4 is not too slow for the problem.
2011-11-02 14:12:32 :D
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.
2011-06-29 14:39:22 pulkit
Can you check submission ID 5313130
my code is TLEing even though it runs in 5 sec in the worst case on my comp...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.