A sled descends a glacier laid out as a grid of R rows and C columns. Each cell holds a non-negative traversal cost added when the sled enters that cell (the starting top-left cell is always entered). From cell (r, c) the sled may move to (r, c+1) (right), (r+1, c) (down), or (r+1, c+1) (diagonally down-right), as long as the destination stays inside the grid. It begins at the top-left cell and must reach the bottom-right cell.
Determine the minimum total cost over all such routes.
Input format
Line 1: two integers R and C.
Next R lines: each contains C non-negative integers, the costs of that row.
Output format
A single integer: the minimum total cost of a right/down/diagonal route from the top-left cell to the bottom-right cell.
Constraints
- 1 <= R <= 100
- 1 <= C <= 100
- 0 <= each cost <= 1000