Cheapest delivery route

Problem

A delivery van crosses a city grid of R rows and C columns. Each block has a toll. The van starts at the top-left block and ends at the bottom-right block, moving only right or down, and pays the toll of every block it visits, including the first and the last. Print the smallest total toll.

Input, output and limits

Input: Line 1: R and C. Then R lines with C tolls each.
Output: One integer: the smallest total toll.
Constraints: 1 ≤ R, C ≤ 100
0 ≤ each toll ≤ 1000

Examples

Example

Input

Output

Route right, right, down, down costs 1 + 3 + 1 + 1 + 1 = 7.

Hints

Try the problem first. Open one hint at a time.

Hint 1

The cheapest cost to reach a block is its toll plus the smaller of the best cost from above and from the left.

Hint 2

Blocks on the top row or left column have only one way in.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Dynamic Programming (2D) problems

Problem

Input, output and limits

Examples

Hints

More Dynamic Programming (2D) problems