Minimum Cost Path in a Grid

You are given a grid with m rows and n columns. Each cell of the grid contains an integer that represents the cost of entering that cell. Your task is to find the minimum cost path from the top-left corner (cell (1,1)) to the bottom-right corner (cell (m,n)).

You can move in four directions: up, down, left, and right. The total cost of a path is the sum of the costs of all cells visited along the path.

The problem can be formulated as finding the path that minimizes the following quantity:

$$\min_{\text{path}}\; \sum_{(i,j) \in \text{path}} grid[i][j].$$

It is guaranteed that grid dimensions and cell costs are such that a solution always exists.

inputFormat

The input is read from standard input and has the following format:

m n
row1_element1 row1_element2 ... row1_elementn
row2_element1 row2_element2 ... row2_elementn
...
rowm_element1 rowm_element2 ... rowm_elementn

Here, the first line contains two integers m and n representing the number of rows and columns respectively. Each of the next m lines contains n space-separated integers representing a row of the grid.

outputFormat

Output a single integer to standard output, representing the minimum cost to travel from the top-left corner to the bottom-right corner.

## sample

3 3
1 3 1
1 5 1
4 2 1

7