URI Online Judge | 1939

Ominobox

By Davi Duarte Pinheiro, Universidade Federal de Pernambuco BR Brazil

Timelimit: 10

The Skyrk planet will never know peace while the evil mage is free. This time, the malicious magician's plan was to arm a bomb in the middle of the largest city on the planet. The Mage enjoys observing the chaos, so instead of blowing up the bomb immediately, he put a timer and left it with a challenge. The bomb has a keyboard, and the solution of the challenge disarms it.

The challenge is called Omnibox; it consists of a rectangular box with some hubs in unit and a collection of all possible N-omnis. Skyrk should drop all omnis somewhere in the box to earn points. The maximum score is the solution of Omnibox.

A N-omni is a collection of unit squares arranged with N sides coincident. A 1-omni is a unit square, and an N-omni is a (N - 1) -omni at least one side thereof connected to a unit square.

omni a
The six possible 3-omnis.
Some of the 19 possible 4-omnis.

The box has a rectangular surface and vertical walls; each of the squares of a grid of Cartesian coordinate system placed on the surface of the box has a non-negative cell unit cubes. The cubes can not be moved.

Skyrk will align each omni with grid squares, and drop it in the box. The omni will fall to touch a cube or background. It is not allowed to Skyrk reflect or rotate the omni, and he must lie completely within the box's boundaries. The number of points obtained after release it is the distance between the omino and the top of the box. After dropping it, Skyrk notes the number of points, remove the omni, and release the next. The final score is the sum of all points.

The clock is ticking and the countdown on the pump says 5:00 (five hours!). You can discover the maximum score Skyrk can get to defuse the bomb and save the fate of the planet from the hands of vile magician?

Input

The first line contains T (T ≤ 200) - the number of challenges, after this line will be T challenges. Each challenge begins with a line with four integers A, C, H and N (1 ≤ R, C, H ≤ 30, 1 ≤ N ≤ 10) - the dimensions of the carton surface are R × L, the height is H, and the order of omnis is N. Each of the next R lines contains C integers Hij (0 ≤ HijH) - the number of cubes in the square (i, j) of the grid.

Output

For each challenge, show a line containing X, where X is the solution of the Omnibox.

Input Sample Output Sample

4

2 2 3 1

1 2

0 3

2 2 3 2

1 2

0 3

2 2 3 3 

1 2

0 3

2 3 5 4

1 2 5

0 3 4

3

3

1

5