Given matrix of size n × m that contains positive integers, not greater than 10000.

The cells are adjacent if their column or row numbers differ by 1. The path from one cell to another passes only through adjacent cells of the matrix.

Find the path with minimum cost between the upper left and lower right corners of the matrix. The cost of the path equals to the sum of matrix elements through the way. It is allowed to move to neighboring cells to the left, right, up and down.

Input

First line contains the numbers n and m (1 ≤ n, m ≤ 10). Then n lines are given, each line contains m numbers.

Output

Print the cost of minimal path.