A warehouse floor is a grid with rows rows and cols columns. Cell (i, j) has a restocking cost. A picker starts at the top-left cell (0, 0) and must reach the bottom-right cell (rows - 1, cols - 1). From any cell (i, j) the picker may move to:

• (i, j + 1) (one column right),
• (i + 1, j) (one row down), or
• (i + 1, j + 1) (one row down AND one column right, diagonally),

as long as the destination cell is within the grid.

Print the minimum possible total restocking cost of a route from (0, 0) to (rows - 1, cols - 1), summing the cost of every cell visited along the way (including both the start and end cells).

Input format

Line 1: two integers rows cols. Next rows lines: cols space-separated integers each -- the restocking costs of that row's cells.

Output format

A single integer: the minimum total restocking cost of a route from the top-left to the bottom-right cell.

Constraints

• 1 <= rows, cols <= 500
• 0 <= cost of each cell <= 1000

2 2
1 2
3 4

5

1 1
5

5