# Problem D

Cops and Robbers

The First Universal Bank of Denview has just been robbed! You want to catch the robbers before they leave the state.

The state of Calirado can be represented by a rectangular
$n$-by-$m$ grid of characters, with the
character in each grid cell denoting a terrain type. The
robbers begin within the cell marked ‘`B`’,
indicating the Bank of Denview. They will then travel across
the state by moving from grid cell to grid cell in the four
cardinal directions (left, right, up, down). (Note that the
robbers pass only through grid edges, and not corners.) If the
robbers manage to leave the state (by crossing any boundary
edge of the grid) they will go into hiding, never to be seen
again. You must stop this.

To catch the robbers, you can set up barricades. Barricades
are placed inside a grid cell, and prevent the robbers from
traveling into the cell (from any direction). Each grid square
consists of a different type of terrain, with different cost
for placing a barricade. You cannot place a barricade on the
bank (‘`B`’) or on any cell containing a dot
(‘`.`’), though the robbers can travel freely
through these cells. Every other cell will contain a lowercase
English letter, indicating a terrain type.

Find the cheapest way to prevent the robbers from escaping Calirado.

## Input

The first line contains three integers $n$, $m$, and $c$ ($1
\le n, m \le 30$, $1 \le c
\le 26$): the dimensions of the grid representing
Calirado, and the number of different terrain types. Then
follows $m$ lines of
exactly $n$ characters
each: the map of Calirado. Each character is either ‘`B`’, ‘`.`’, or one of the first
$c$ lowercase letters of
the English alphabet. Calirado is guaranteed to contain exactly
one bank. After the grid, there is a line containing
$c$ space-separated
integers $1 \leq c_ i \leq 100\,
000$, the costs of placing a barricade on a grid cell of
each terrain type. $c_1$
is the cost for terrain type ‘`a`’,
$c_2$ is the cost for
‘`b`’, and so forth.

## Output

Print one integer, the minimum total cost of the barricades
that you need to place to prevent the robbers from escaping. If
there is no way to prevent the robbers from escaping, print
`-1` instead.

In the first example, the minimum cost is to barricade the central three squares on each side of the bank for a total cost of $12$.

In the second example, since the bank is on the border, there is no way to prevent the robbers from escaping the state.

In the third example, we must prevent the robbers from
leaving the bank to the top, bottom, and right, or else we
cannot prevent them from leaving the state. To the left,
however, it is cheaper to allow passage through the ‘`b`’ cell, and then barricade in each of the three
directions from there. The total cost is $7 + 5 + 7 + 3(1) = 22$.

Sample Input 1 | Sample Output 1 |
---|---|

5 5 1 aaaaa a...a a.B.a a...a aaaaa 1 |
12 |

Sample Input 2 | Sample Output 2 |
---|---|

2 2 1 aB aa 1 |
-1 |

Sample Input 3 | Sample Output 3 |
---|---|

4 3 3 .abc abBc .abc 1 7 5 |
22 |