Cheapest Path Down a Grid

A grid has \(R\) rows and \(C\) columns, and each cell holds an integer cost, which may be negative. A path starts at any cell of the top row and moves down one row at a time. From column \(c\) it may go to column \(c - 1\), \(c\) or \(c + 1\) of the next row, as long as it stays inside the grid. It ends when it reaches a cell of the bottom row. The cost of a path is the sum of every cell it visits, the first and the last included.

Implement min_descent_cost(grid) returning the smallest cost of any path.

One way to picture it: a delivery drone starts above the top row with some power \(P\), and every cell it flies through drains that cell's cost (a negative cost recharges it). The most power it can have left on the bottom row is \(P\) minus the answer, which may be negative.

Examples

min_descent_cost([
    [3, 8, 6, 2],
    [7, 1, 9, 5],
    [4, 6, 2, 8],
    [9, 3, 7, 1],
])
# 7  (3 -> 1 -> 2 -> 1; a drone starting with 100 has 93 left)

min_descent_cost([
    [4, -2, 7],
    [-5, 3, 1],
    [2, -6, 0],
])
# -13  (-2 -> -5 -> -6)

In the first example the cheapest top cell is the 2 in the last column, but every path from it costs at least 10.

Constraints

• \(1 \le R, C \le 500\). A grid with one row is a path of one cell.
• Every cost is between \(-10^9\) and \(10^9\). A total can reach \(5 \times 10^{11}\) in size, so it needs a 64-bit integer.
• There are up to \(C \cdot 3^{R-1}\) paths. Trying them all, or a recursion that recomputes the same cells, will not finish on the large tests.

In C++

long long min_descent_cost(const std::vector<std::vector<long long>>& grid);