Shopping

A city is laid out as a grid with $H$ rows and $W$ columns. Each cell either holds one shop or is empty. Every shop sells a different item, and the price of an item is an integer from 1 to 9.

You start at cell $(1, 1)$ and walk to cell $(H, W)$. From a cell you may move only to the cell on its right or the cell below it.

Every time you arrive at a cell, including the starting cell, you shop in this order.

1. If the cell you arrived at holds a shop you have not bought from yet, you buy its item.
2. Collect every cell that shares a side with the cell you arrived at and holds a shop you have not bought from yet. If there is at least one such cell, choose exactly one of them, skip it, and buy the item of every other collected cell. If there is no such cell, you buy nothing.

You buy from each shop at most once. In step 2 you choose the cell to skip freely each time. A shop you skipped is bought later anyway if you arrive next to it again.

Print the smallest amount of money you spend when the route and every skipped cell are chosen as well as possible.

The first line has two integers $H$ and $W$, the number of rows and the number of columns, separated by a space. ($3 \le H \le 1000$, $3 \le W \le 1000$)

Each of the next $H$ lines has one string of length $W$. The $j$-th character of the $i$-th line describes cell $(i, j)$. A "." means the cell has no shop. A digit from "1" to "9" means the cell has a shop and the digit is the price of its item.

Print the smallest amount of money you spend.