Ominobox

Time limit10sMemory limit512 MB

Summary

For every fixed N-omino placement in a small grid, the drop score is H minus the maximum stack height covered; sum the best placement score over all N-ominoes.

Level: Hard8 of 10
Topics: Brute force, Implementation, Simulation, Recursion
Solved: No attempts yet

Problem

An evil wizard planted a bomb in the middle of the city and set a timer on it. Next to the bomb he left a keypad and a puzzle. Entering the answer to the puzzle stops the bomb. The puzzle is called Ominobox.

An Ominobox consists of a box holding some unit cubes and a set of pieces that contains every possible N-omino exactly once. You drop the pieces into the box one at a time to score points, and the answer to the Ominobox is the largest total score you can get.

An N-omino is a set of $N$ unit squares joined along their edges. A 1-omino is a single unit square, and an N-omino is an (N-1)-omino with one more unit square attached along an edge. Two pieces are the same piece when one is a translation of the other, and two pieces that match only after a rotation or a reflection count as different pieces. The figure below shows all six 3-ominoes and some of the nineteen 4-ominoes.

The floor of the box is an $R \times C$ grid and the four walls have height $H$ . Cell $(i, j)$ of the grid holds a stack of $H_{ij}$ unit cubes, and the stacked cubes cannot be moved.

You align a piece with the grid, place it above the box and let it fall. Rotating or reflecting a piece is not allowed, and the whole piece must stay inside the floor grid. The piece falls until it touches a stack of cubes or the floor. So if $t$ is the largest $H_{ij}$ among the cells the piece covers, the bottom face of the piece rests at height $t$ , and the score for that drop is $H - t$ , the distance from the bottom face of the piece to the top rim of the box. After writing the score down you take the piece back out, so the cubes inside the box stay where they are the whole time. A piece that has no place inside the floor grid scores 0.

Compute the answer to the Ominobox, the total score when every piece is dropped in its best place.

Input

The first line contains the number of challenges $T$ ( $1 \le T \le 200$ ).

Then $T$ challenges follow. The first line of each challenge contains four integers $R$ , $C$ , $H$ and $N$ ( $1 \le R, C, H \le 30$ , $1 \le N \le 10$ ). The floor of the box is an $R \times C$ grid, the walls have height $H$ , and the pieces are the N-ominoes. Each of the next $R$ lines contains $C$ integers. The $j$ -th integer on the $i$ -th line is $H_{ij}$ , the number of cubes on cell $(i, j)$ ( $0 \le H_{ij} \le H$ ).

Output

For each challenge, print the answer to the Ominobox on its own line.

Examples1

Example 1

Input

Expected output