A scree slope is modeled as a grid of R rows and C columns; each cell holds an integer weight (which may be negative). A rock is released from any single cell in the top row and falls to the bottom row. From cell (r, c) it moves to one of (r+1, c-1), (r+1, c), or (r+1, c+1), provided that cell stays within the grid. The total of a fall is the sum of every cell it occupies, including the starting top-row cell and the final bottom-row cell.
Over every choice of starting column and every valid sequence of moves, determine the minimum possible total.
Input format
Line 1: two integers R and C.
Next R lines: each contains C integers, the weights of that row.
Output format
A single integer: the minimum total of a fall from the top row to the bottom row.
Constraints
- 1 <= R <= 100
- 1 <= C <= 100
- -1000 <= each weight <= 1000