김지민의 침략

임한수가 다스리는 왕국은 반란군 김지민의 침략으로 위협받고 있다. 김지민의 군대는 왕국의 모든 경계에서 수도를 향해 들어오려 한다. 임한수는 수도로 가는 모든 길을 막기 위해 지도 위의 칸 몇 곳에 장애물을 설치하려고 한다.

지도는 N행 M열의 직사각형 격자이다. 수도는 *, 이미 지나갈 수 없는 칸은 -, 나머지 칸은 지형을 나타내는 알파벳 대문자로 표시된다. 군대는 상하좌우로 변을 공유하는 인접한 칸으로만 이동할 수 있다.

장애물은 알파벳 지형 칸에 설치할 수 있으며, 각 지형마다 필요한 장애물의 크기가 정해져 있다. 경계 칸에서 수도까지 갈 수 있는 모든 경로가 - 또는 설치한 장애물로 막혀야 한다. 먼저 설치하는 장애물의 개수를 최소로 하고, 그런 방법이 여러 가지라면 장애물 크기의 합이 최소가 되도록 한다. 그때 장애물 크기의 합을 구하라.

첫째 줄에 N과 M이 주어진다. N과 M은 3 이상 50 이하인 자연수이다.

둘째 줄부터 N개의 줄에 지도가 주어진다. 마지막 줄에는 26개의 정수가 주어진다. 첫 번째 정수는 A 지형에 필요한 장애물의 크기, 두 번째 정수는 B 지형에 필요한 장애물의 크기이며, 이후도 알파벳 순서대로 대응된다.

수도는 정확히 하나 존재하며, 첫 번째 행, 마지막 행, 첫 번째 열, 마지막 열에는 있지 않다. 장애물의 크기는 모두 1 이상 1,000,000 이하이다.

첫째 줄에 조건을 만족하도록 설치한 장애물들의 크기 합을 출력한다.