Singapore Tour

Time limit2sMemory limit512 MB

Summary

Start at C, collect values from up to 14 grid spots with per-step cost 2, and return for the maximum net score.

Level: Medium6 of 10
Topics: Dynamic programming, BFS, Graph
Solved: No attempts yet

Problem

A tourist has a map of Singapore drawn as an $R \times C$ grid with $1 \le R, C \le 20$ . Every cell is one of the following.

~ (tilde) is water.
. is land.
A digit from 2 to 9 is an attractive spot.
C is Changi Airport.

The map below is a $3 \times 5$ grid with one C and two attractive spots labeled 5 and 6.

~.~.~
6.~5.
~..C~

There are $N$ attractive spots with $0 \le N \le 14$ . The digit written on spot $i$ is its satisfaction value $S_i$ with $2 \le S_i \le 9$ , so a spot labeled 5 has $S_i = 5$ . The tourist gains $S_i$ points when he visits spot $i$ .

The tourist moves one cell at a time in the four directions (north, east, south, west) and never enters a water cell. Every cell that is not water is passable, whether it is land, an attractive spot, or Changi Airport. Singapore is a well built city, so from any non-water cell the tourist reaches every other non-water cell. Walking is tiring, so each step costs $2$ satisfaction points. Rows and columns are numbered from 0. On the map above, walking from the C at row 2, column 3 to the 6 at row 1, column 0 along a shortest path takes four steps and costs $4 \times (-2) = -8$ points.

The tourist lands at Changi C, tours the spots he wants, and returns to C to fly home. He may cross any non-water cell as many times as he likes, but he collects the satisfaction of each spot only once. Given the map, what is the largest total satisfaction he can reach?

On the map above, the tour C → 6 → 5 → C gives $4 \times (-2) + 6 + 5 \times (-2) + 5 + 1 \times (-2) = -9$ points. The tour C → 5 → C gives $1 \times (-2) + 5 + 1 \times (-2) = 1$ point, and that is the largest value over all tours. The tourist skips 6 because it is not worth the walk.

Input

The first line contains the integers $R$ and $C$ separated by one space. Each of the next $R$ lines contains exactly $C$ characters. The input holds exactly one C and between 0 and 14 attractive spots.

Output

Print one integer, the largest total satisfaction the tourist can reach. He may visit no spot at all, so the answer is never negative.

Examples2

Example 1
Input
```
3 5
~.~.~
6.~5.
~..C~
```
Expected output
```
1
```
Example 2
Input
```
1 3
9C9
```
Expected output
```
10
```