Minimum Travel Cost

You are given a grid of size \(n \times m\), where each cell contains a non-negative integer representing the travel cost to pass through that cell. Your task is to determine the minimum total cost required to travel from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((n-1, m-1)\)).

You can move in four directions: up, down, left, and right. It is guaranteed that there is always at least one valid path from the start to the destination.

inputFormat

The input is given via standard input (stdin) and has the following format:

n m
row1_element1 row1_element2 ... row1_elementm
row2_element1 row2_element2 ... row2_elementm
... 
rown_element1 rown_element2 ... rown_elementm

Here, the first line contains two integers \(n\) and \(m\) which denote the number of rows and columns, respectively, followed by \(n\) lines each containing \(m\) space-separated integers that represent the grid.

outputFormat

Print a single integer to standard output (stdout), which is the minimum travel cost from the top-left corner to the bottom-right corner of the grid.

3 3
1 3 1
1 5 1
4 2 1

7