Limits 1s, 512 MB

Mr. Hikiko recently downloaded a strange game on his phone from a store. This game is quite interesting, but he is too lazy to play a game level by level. So, he decided to write a code, which will complete all levels of this game. Now, let me tell you about his laziness a bit more. He doesn't even want to write this code himself. So, he is looking for help. Can you help him?

Rules of this game are straight forward. You will be given a grid of n rows and m columns. Each cell in this grid will have a point.

You will start from row 1. You have to select a cell. Then you have to select k consecutive cells of this row including the selected cell and collect points of these cells. Then you have to make a jump from any selected cell of this row to the any cell of the next row as if their distance is less or equal to l. Here distance means, the absolute difference of column number between these two cells. If you make a jump from cell1,1 to cell2,4 then the distance will be |1 - 4| = 3. After making a jump, you have to select k consecutive cells of this row including the cell you jumped into. You will collect points from these cells and have to make another jump to the next row. You will repeat this process until you reached to the nth row.

You can start with any cell for the first row. When you are done with all the rows, what is the maximum total points you can collect?

Input

Input will contain T (1 ≤ T ≤ 10) Test cases.
Each case will start with four integer n, m, k (1 ≤ k ≤ m), l (0 ≤ l < m).
Next, the grid will be given. Points in each cell will be between 0 and 106.

Output

For each test case, print the maximum total points you can collect.

Sample

InputOutput
1
3 6 2 2
2 1 3 0 2 4
5 5 4 2 5 4
10 3 5 4 2 4
28

Solution for the Sample Case:


Submit

Login to submit.

Statistics

57% Solution Ratio
Riaz_BSMRSTUEarliest, Aug '20
EgorKulikovFastest, 0.1s
serotoninLightest, 8.3 MB
serotoninShortest, 984B
Toph uses cookies. By continuing you agree to our Cookie Policy.