Minimum Path Sum

Problem statement

A robot crosses a rectangular cost map from its upper-left cell to its lower-right cell. Entering a cell adds its cost, and the robot may move only right or down. Your task Find the minimum sum of cell values along a permitted path, including both the starting and destination cells. Important details Diagonal, upward and leftward moves are forbidden. A one-cell map charges that cell once. Costs are nonnegative, but choosing the cheapest immediate neighbor is not guaranteed to minimize the full route. Worked example For rows [1, 3] and [2, 1], moving down then right costs 1 + 2 + 1 = 4. Moving right then down costs 5, so print 4.

Input format

First line: rows columns. Next rows lines: cell costs.

Output format

Print the minimum path sum.

Constraints

1 <= rows, columns <= 200; 0 <= costs <= 200.

Sample input

2 2
1 3
2 1

Sample output

4