Maximize Score in Super Reward Mode

You are playing a variant of the popular game where the goal is to collect as many points as possible by running along a grid and optionally performing jumps. The game interface is represented by a grid with n columns (numbered 1 to n) and m rows (numbered 1 to m). The bottom row is row 1, and the top row is row m. Each cell in the grid contains an integer reward (between -1 and 1000); a value of -1 indicates that the cell is blocked and cannot be stepped on.

Your character starts at cell (1, 1) (i.e. column 1, bottom row) and must reach column n on the bottom row. Along the way, you may move in one of two ways:

1. Walk: move from cell (x, 1) to cell (x+1, 1). This collects the reward from the destination cell. You cannot walk if the destination cell is blocked.
2. Jump: before the game begins you set two jump parameters:
   • H – the jump height parameter
   • K – the maximum number of consecutive jumps (chain jumps) allowed (1 ≤ K ≤ 5)
   A normal jump (when K = 1) is performed from the ground (row 1) as follows. Suppose you initiate a jump at cell (x, 1). The jump follows a parabolic trajectory that lasts for exactly 2*H steps advancing horizontally. At step i (0 ≤ i ≤ 2*H) the character lands in column x + i at row
       row = 1 + { i, if 0 ≤ i ≤ H; 2*H - i, if H < i ≤ 2*H }.
   Thus, the full trajectory (including the starting cell) is:
   (x, 1), (x+1, 1+1), (x+2, 1+2), ..., (x+H, 1+H), (x+H+1, 1+H-1), ..., (x+2*H, 1).
   All cells along the jump arc must be within the grid and none can be blocked (i.e. have a reward of -1).

You are also allowed to perform chained jumps: from your current position on the ground you may initiate a move consisting of r consecutive normal jumps, where 1 ≤ r ≤ K. When performing consecutive jumps, you start the first jump from your current cell, then, immediately after landing you start the next jump from that landing cell. Note: When chaining, the landing cell of a jump would be counted twice if the normal jump score is simply summed up. To avoid double‐counting, treat the starting cell of each jump (except for the first) as already collected. In other words, if singleJump(x) is the total reward collected when performing a normal jump starting at column x (which includes the reward at (x,1)), then the reward collected by chaining r jumps starting at column x is computed as:

Reward = [singleJump(x) - reward(x,1)] + [for each jump j from 2 to r: (singleJump(x + (j-1)*2*H) - reward(x+(j-1)*2*H)] + reward(x + r*2*H)

After a jump (or chained jump) from a cell in column x, you land at cell (x + r*(2*H), 1) where the reward in that cell is collected (if not already counted) and then you continue your journey from there. Your overall score is the sum of rewards collected along the path (including the start and all visited cells). Your task is to compute the maximum score obtainable when moving from column 1 to column n along the bottom row (row 1) using any sequence of moves (walks and/or jumps). If no valid path exists, output -1.

Important: The jump parameters H and K are provided as part of the input. Also, since a jump (or chained jump) uses a fixed trajectory, you must check that all cells along the jump arc are within the grid and not blocked.

Example 1: Suppose H = 2 and K = 1. Then a normal jump from (1,1) covers cells: (1,1), (2,2), (3,3), (4,2), (5,1).

Example 2: With H = 2 and K = 2, a chained jump starting at (1,1) might follow: first jump: (1,1), (2,2), (3,3), (4,2), and immediately chain a second jump: (5,3), (6,4), (7,3), (8,2), (9,1).

inputFormat

The first line contains four integers: n (number of columns), m (number of rows), H (jump height parameter) and K (maximum number of consecutive jumps allowed).

Then follow m lines, each containing n integers. The first of these lines represents the top row (row m) of the grid, and the last line represents the bottom row (row 1). Each integer is between -1 and 1000, where -1 indicates a blocked cell.

It is guaranteed that the starting cell (1,1) (i.e. first column of the bottom row) is not blocked and that the jump parameters are such that any jump performed will not go out of the vertical bounds of the grid.

outputFormat

Output a single integer – the maximum score obtainable when moving from cell (1,1) to some cell in column n on the bottom row using a sequence of moves (walks and/or jumps). If no valid path exists, output -1.

sample

5 3 2 1
1 2 3 4 5
2 2 2 2 2
3 1 0 1 3

13