Shopping

Time limit2sMemory limit512 MB

Summary

Choose a right-and-down path from (1,1) to (H,W) that minimizes the price of visited and neighboring shops when one neighbor shop can be skipped at each step.

Level: Hard8 of 10
Topics: Dynamic programming, Shortest path
Solved: No attempts yet

Problem

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.

If the cell you arrived at holds a shop you have not bought from yet, you buy its item.
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.

Input

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.

Output

Print the smallest amount of money you spend.

Examples2

Example 1
Input
```
5 5
..483
.59.9
3.866
79...
4.8..
```
Expected output
```
20
```

Example 2

Input

Expected output