Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Mr. Hikiko and a Strange Game (Easy)

By Riaz_BSMRSTU · Limits 1s, 512 MB

Easy Version: 40 Points

The only difference between easy and hard versions is the constraint on n and m.

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.

Constraint

1 ≤ n, m ≤ 102.

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:


    Discussion

    Statistics


    50% Solution Ratio

    Riaz_BSMRSTUEarliest, 1M ago

    EgorKulikovFastest, 0.0s

    conan_0Lightest, 262 kB

    serotoninShortest, 984B

    Submit

    Login to submit

    Editorial

    This problem can be solved with Dynamic Programming. Let’s define DP[i][j] is the maximum points we...