Description

A temple fair is being held in the city. There are many stalls at the fair. The venue forms a large grid with $H$ stalls from north to south and $W$ stalls from west to east. A stall at the $i$-th row from the north and the $j$-th column from the west is denoted by $(i, j)$.

The girl starts at position $(1, 1)$ in the fair and can only move east or south, continuing until she reaches $(H, W)$ to meet Xiao B. The stalls at $(1, 1)$ and $(H, W)$, as well as each of their four directly adjacent stalls (north, south, east, west), are not open. There may also be other stalls that are not open elsewhere.

The girl is a foodie. Whenever she arrives at a stall, she cannot resist the snacks there. If the stall is open and she has not bought from it before, she will buy the snack at this stall. Regardless of whether the current stall is open, the aromas from its four directly adjacent stalls are tempting as well. Among its directly adjacent open stalls that have not been bought yet (suppose there are $r$ of them), she will buy snacks from exactly $r - 1$ of these adjacent stalls. She then continues moving east or south. She will never buy from the same stall more than once.

Although she is a foodie, her pocket money is limited. She cannot control herself and will keep buying. Therefore, she wants to know the minimum total amount of money she will spend.

Input Format

The first line contains two integers $H$ and $W$.

The next $H$ lines each contain a string of length $W$ without spaces. Each character is one of $1 \sim 9$ or .. A digit represents the price, and . represents a stall that is not open.

Output Format

Output a single integer, the minimum amount of money spent.

5 5
....7
.21.8
9346.
..45.
.8...

9

Hint

5 5
oooo7
.2xoo
9346o
..45o
.8..o

Explanation of the illustration: o marks the route the girl takes, and x marks snacks she buys incidentally. When she reaches $(2, 4)$, the left, down, and right neighbors are open and not yet bought, so she buys the left and right ones, then continues along the route. After that, the route does not pass any not-yet-bought stalls, and each time the number of open and not-yet-bought adjacent stalls is at most $1$, so she buys none of them.

Constraints:

• For $20\%$ of the testdata, the number of open stalls does not exceed $20$.
• For $100\%$ of the testdata, $3 \le H, W \le 1000$.

Special note: The testdata was generated on Windows. Line endings in the input may be \r\n (two characters) or \n. The judge runs on Linux. Please be careful. Appeals like “it passes locally but gets WA on the judge” will not be accepted.

Reference input method (excerpt from std):

for (i = 0; i < H; ++i) {
	scanf("%s", in);
	for (j = 0; j < W; ++j) {
		shop[i][j] = blabla..
	}
}

Translated by ChatGPT 5