You are given a grid of non-negative integers. Starting from the top-left cell, you want to reach the bottom-right cell, moving only right or down by one cell at a time.

The cost of a path is the sum of the values of every cell it visits, including both the start and end cells. Find the minimum possible path cost.

Input format

Line 1: two integers rows and cols. The next rows lines: each contains cols non-negative integers, the grid in row-major order.

Output format

A single integer: the minimum sum of cell values over all right/down paths from the top-left cell to the bottom-right cell.

Constraints

• 1 ≤ rows ≤ 200
• 1 ≤ cols ≤ 200
• 0 ≤ each cell value ≤ 1000
• A path always exists (there are no blocked cells).

3 3
1 3 1
1 5 1
4 2 1

7

2 3
1 2 5
3 2 1

6