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