Skyrk’s planet will never know peace while evil Mago is lurking out there. This time, Mago’s malicious scheme was to set up a bomb in the middle of the planet’s biggest city. Mago relishes seeing chaos, so instead of detonating the bomb right away, he put a timer on it and left it together with a puzzle. The bomb has a keypad, and the solution to the puzzle disarms the bomb. The puzzle is called Ominobox; it consists of both a rectangular box with some unit cubes inside and a collection of all possible N-ominoes. Skyrk has to drop every omino somewhere into the box to score points. The maximum score is the solution to the Ominobox. An N-omino is a collection of N unit squares arranged with coincident sides. A 1-omino is a unit square, and an N -omino is an (N − 1)-omino with at least one of its sides joined to a unit square. The six possible 3-ominos Some of the 19 possible 4-ominos The box has a rectangular surface and vertical walls; each of the squares of a Cartesian coordinate grid system placed on the box’s surface has a non-negative pile of unit cubes. The cubes cannot be moved. Skyrk will align every omino with the grid squares, and drop it into the box. The omino will fall until it touches a cube or the bottom. Skyrk is not allowed to reflect or rotate the omino and it must lie completely inside the boundaries of the box. The number of points earned with a drop is the distance between the omino and the top of the box. After the drop, Skyrk writes down the points, removes the omino, and drops the next one. The final score is the sum of all points. The clock is ticking and the countdown on the bomb says 5:00 (five hours!). Can you find out the maximum score Skyrk can get, so that he can disarm the bomb and save the planet’s fate from the hands of vile Mago? Input The first line in the input contains T (T ≤ 300) — the number of test cases, after this line T test cases follows. Each test case starts with a line with four integers R, C, H, and N (1 ≤ R,C,H ≤ 30; 1 ≤ N ≤ 10) — the box surface dimensions are R × C, the height is H, and the ominoes’ order is N. Each of the next R lines contains C integers Hi,j (0 ≤ Hi,j ≤ H) — the number of cubes at grid square (i,j). Output For each test case, print a line containing X, where X is the solution to the Ominobox. Notes
2/2 In the first test case, Fig. 1 shows the best placement of the only 1-omino. The omino hits the bottom of the box at position (1,0) and has a distance of 3 to the top of the box. This placement yields a total of 3 points. In the second test case, Fig. 2 and Fig. 3 show the best placement of the two 2-ominoes. In Fig. 2 the omino hits a pile of cubes of height 1 at position (0,0) and has a distance of 2 to the top of the box. In Fig. 3 the omino hits a pile of cubes of height 2 at position (0,1) and has a distance of 1 to the top of the box. These placements yield a total of 3 points. In the third test case, Fig. 4 shows the best placement of the only 3-omino that can fit inside the box. This placement yields a total of 1 point. In the fourth test case, Fig. 5-8 show the best placement of the four 4-ominoes that can fit inside the box. These placements yield a total of 5 points. Sample Input 4 2231 12 03 2232 12 03 2233 12 03 2354 125 034 Sample Output 3 3 1 5