Problem Statement

You are given an R × C grid of integers and two column indices p and q . A valid path can be formed in either of the following ways: Start at cell (0, p) (first row, column p ) and end at any cell in the last row. Start at cell (R - 1, q) (last row, column q ) and end at any cell in the first row. From a cell (r, c) , you may move to any of its 8 neighboring cells (horizontal, vertical, or diagonal), provided the move stays within the grid. A valid path must satisfy the following condition: It must contain exactly one cell from each row. Equivalently, the row index must change by exactly 1 at every step, so horizontal moves are not allowed. The score of a path is the sum of the values of all cells in the path. Return the maximum possible path sum among the two possible starting directions. Example Grid = 1 2 3 4 10 6 7 8 9 p = 2 q = 1 Starting from (0, 2) , one optimal path is 3 → 10 → 9 with sum 22. Starting from (2, 1) , one optimal path is 8 → 10 → 3 with sum 21. Output: 22 Constrai