题目背景

王国边境传来急报：蛮族军队正从四面八方向王都逼近。

王国的疆域可以抽象成一张矩形网格地图。地图上有高山、峡谷等无法通行的区域，也有草原、森林、沼泽等不同类型的可通行地形。王都位于地图中的某个格子。

为了守住王都，统帅可以在部分可通行格子上部署防御分队。每个分队都需要一名指挥官，而合格的指挥官十分稀缺，因此统帅首先希望部署的分队数量尽可能少；在此前提下，还希望所有分队的总人数尽可能少。

请你计算，在满足上述要求的情况下，至少需要部署多少名士兵。

题目描述

给定一个大小为 $H\times W$ 的王国地图。

地图中的字符含义如下：

• *：王都；
• -：无法通行的地形；
• A 到 Z：不同类型的可通行地形。

敌人可以从任意一个位于地图边界、且可以通行的格子进入王国。之后，敌人每次可以向上、下、左、右移动到一个相邻的可通行格子。

你可以在任意标有大写字母的格子上部署一个防御分队。部署分队后，该格子将不能被敌人通过。不能在王都或不可通行格子上部署分队。

对于地形类型 A 到 Z，分别给出在该类地形上部署一个分队所需的人数。

你需要选择若干个格子部署分队，使得敌人无法从地图边界到达王都。

优化目标按如下顺序确定：

1. 部署的分队数量最少；
2. 在分队数量最少的前提下，所有分队的总人数最少。

请输出第二个目标对应的最小总人数。

如果在不部署任何分队的情况下，敌人本来就无法到达王都，则输出 $0$。

输入格式

第一行包含两个整数 $H,W$，表示地图的行数和列数。

接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串，描述王国地图。

最后一行包含 $26$ 个整数：

$$d_A,d_B,\ldots,d_Z,$$

其中 $d_X$ 表示在地形类型 X 上部署一个防御分队所需的人数。

输出格式

输出一行一个整数，表示在部署分队数量最少的前提下，所需的最小总人数。

样例 1

输入

3 3
ABA
A*A
AAA
1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出

5

解释

王都四周的四个可通行格子必须全部被封锁。它们的地形类型分别为 B、A、A，因此总人数为

$$2+1+1+1=5.$$

样例 2

输入

4 4
CCCC
-BAC
-*AC
--AC
5 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出

25

解释

虽然可以在边界上部署 $7$ 个较小的分队，总人数仅为 $7$，但首要目标是使分队数量最少。

只需在王都附近的 A、B 两个格子上分别部署一个分队，共使用 $2$ 个分队，总人数为

$$5+20=25.$$

数据范围

对于全部测试数据：

$$3\le H,W\le 50,$$

• 地图中恰好包含一个 *；
• * 不位于地图边界；
• 地图中的字符只可能是 A 到 Z、- 或 *；
• 每一行地图的长度均为 $W$；
• 对任意地形类型 $X$，满足

$$1\le d_X\le 10^6.$$