# Practice on Toph

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

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

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 **cell _{1,1}** to

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 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 **10 ^{6}**.

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

Input | Output |
---|---|

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: |

55% Solution Ratio

Riaz_BSMRSTUEarliest,

EgorKulikovFastest, 0.1s

serotoninLightest, 8.3 MB

serotoninShortest, 984B

Login to submit

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