Problem Description

JOI-kun lives in the city of IOI, which is divided into a grid of $H$ rows and $W$ columns. The cell at the $i$-th row from the north and the $j$-th column from the west is denoted as $(i, j)$. A large festival is currently being held in IOI city to commemorate an international programming contest. Some cells have food stalls, each selling different kinds of snacks. There are no stalls in cells $(1, 1)$, $(H, W)$, and their adjacent cells.

JOI-kun moves from cell $(1, 1)$ to cell $(H, W)$. To shorten the travel time, he only moves east or south. JOI-kun loves snacks, so whenever he enters a cell, he takes the following actions in order:

• If the current cell has a stall selling a snack he hasn't bought yet, he buys the snack.
• If any of the adjacent cells (north, south, east, west) have stalls selling snacks he hasn't bought yet, he calls the vendors from all but one of these stalls to buy their snacks.

JOI-kun never buys the same kind of snack more than once.

Given the size of IOI city, the locations of the stalls, and the prices of the snacks at each stall, find the minimum total amount JOI-kun spends on snacks while moving from cell $(1, 1)$ to cell $(H, W)$.

Input Format

The input consists of $1 + H$ lines.

The first line contains two integers $H, W$ ($3 \leq H \leq 1,000$, $3 \leq W \leq 1,000$), indicating that IOI city is divided into $H \times W$ cells.

The following $H$ lines each contain a string of $W$ characters, representing the information of each cell in IOI city. The $j$-th character of the $i$-th line ($1 \leq i \leq H$, $1 \leq j \leq W$) is . if there is no stall in cell $(i, j)$. If there is a stall, it is one of 1, 2, ..., 9, representing the price of the snack sold at that stall.

Among the five input datasets, in input 1, the number of cells with stalls is at most 20.

Output Format

Output the minimum total amount JOI-kun spends on snacks while moving from cell $(1, 1)$ to cell $(H, W)$ in one line.

Sample Input and Output

Sample Input #1

5 5
..483
.59.9
3.866
79...
4.8..

Sample Output #1

20

Sample Input #2

12 10
..498522.4
.633527629
54.4621596
634.213458
1924518685
7739539767
276155.3.6
87716372.2
.858877595
7998739511
3438.5852.
568.9319..

Sample Output #2

63

Notes/Hints

Sample Explanation 1

In sample input/output 1, moving in the order of cells $(1, 1)$, $(2, 1)$, $(3, 1)$, $(3, 2)$, $(4, 2)$, $(4, 3)$, $(4, 4)$, $(4, 5)$, $(5, 5)$ and buying snacks from stalls in cells $(3, 1)$, $(3, 3)$, $(4, 2)$ results in the minimum total amount spent on snacks.

见题面 Input 部分

见题面 Output 部分