Maximum Falling Path with Limited Vertical Jumps and Bonus Scoring

Problem: Maximum Falling Path with Limited Vertical Jumps and Bonus Scoring You are given an integer matrix board of size N x M. A player starts from the cell (0, p) in the top row and wants to reach any cell in the last row while maximizing the total score. From cell (i, j), the player may move to one of the following cells, as long as the destination is inside the grid: (i + 1, j - 1): down-left (i + 1, j): down (i + 1, j + 1): down-right (i + 2, j): special vertical jump The special jump (i + 2, j) can be used at most K times in the whole path. The base score of a path is the sum of all visited cell values. There are also two bonus rules: If two consecutively visited cells have the same value, gain an extra +X points. If three consecutively visited cells have strictly increasing values, gain an extra +Y points. Return: The maximum score achievable from (0, p) to the last row. One path that achieves this maximum score. The number of distinct maximum-score paths modulo 10^9 + 7. Two paths are considered different if their coordinate sequences are different. If the bonus rules are not needed, set X = 0, Y = 0. Input Format N M K p X Y board[0][0] board[0][1] ... board[0][M-1] ... board[N-1][0] ... board[N-1][M-1] Output Format max_score count_mod L r0 c0 r1 c1 ... rL-1 cL-1 where: max_score is the maximum total score. count_mod is the number of maximum-score paths modulo 10^9 + 7. L is the length of the printed path. The next L lines describe one maximum-score path. Constraints 1 <= N, M <= 200 0 <= p < M 0 <= K <= N -10^9 <= board[i][j] <= 10^9 0 <= X, Y <= 10^9 Example Input: 4 4 1 1 0 0 1 2 3 4 5 6 1 2 7 8 9 1 3 2 5 6 One valid output: 23 1 4 0 1 1 1 2 2 3 3 Example Input 4 4 1 1 0 0 1 2 3 4 5 6 1 2 7 8 9 1 3 2 5 6 Output 23 1 4 0 1 1 1 2 2 3 3