Bob is going on a date with Alice tonight. Unfortunately, he hasn't showered recently, and the stench radiating from his person is sufficient to render a grown adult unconscious at a range of two metres. Not wanting his date to end the second he sees Alice, Bob has decided to return home to shower and prepare. However, when he gets to his property he finds that Mallory has taken the liberty of releasing a herd of magic cattle into his lot.

For the past few hours, these magic cattle have been wandering around, eating his grass, and depositing "special mud" all over the place. Now, Bob knows that when he crosses the lawn, he may be forced to step in this special mud, which will stick to him, and can only be removed by special soap.

To make things easier for himself, Bob has divided the lawn into an ~n \times m~ ~(1 \le n, m \le 50)~ grid and calculated that for each square, he will need to wash himself with ~k~ ~(0 \le k \le 9)~ additional bars of soap if he steps in it. Bob can move forwards, backwards, and sideways, but not diagonally.

Since he doesn't want to waste soap, help him calculate the minimum total bars of soap he will need if he takes the best route.

Input Specification

The first line contains ~n~, the number of rows in the grid, followed by ~m~, the number of columns in the grid, on the second line.

The next ~n~ lines each contain a sequence of ~m~ digits, each representing the amount of "special mud" in the ~m^\text{th}~ column of the ~n^\text{th}~ row.

Output Specification

A single integer, the total amount of soap Bob will need to wash off the mud if he takes the best route from the entrance of his lot (at the first cell on the first row) to the door of his house (the last cell of the last row).

Sample Input

6
5
12345
12345
12345
12345
12345
66666

Sample Output

25