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

2 2
1 9
9 1

2

1 3
2 3 4

9