시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 41 10 8 53.333%

문제

임한수가 통치하는 왕국이 반란군 김지민의 침략에 의해 위협받고 있다. 김지민은 생김새와 어울리지 않지만, 영리하게도 모든 방향에서 임한수의 왕국을 침략하고 있다. 임한수는 이 야만인들이 수도에는 들어오지 못하게 해야된다고 결정했다. 일단 임한수는 왕궁의 지도를 펼쳤다. 지도는 N*M크기의 직사각형 모양이고, 수도는 '*'로 표시되어 있고, 지나갈 수 없는 정사각형은 '-'로 표시되어 있다. 그리고 나머지 정사각형은 지형을 상징하는 알파벳 대문자이다.

임한수는 장애물을 적절히 배치해서 경계에서부터 수도로 갈 수 없도록 할 것이다. 즉, 야만인들이 수도에 갈 수 없어야하기 때문에, 경계선에서 수도로 가는 모든 경로가 지나갈 수 없는 정사각형 또는 장애물로 막혀있어야 한다. 김지민의 군대는 동서남북으로만 이동할 수 있고, 변을 공유하는 정사각형으로만 이동할 수 있다. 따라서, 모든 경로는 변을 공유하는 정사각형의 집합이다.

각각의 지형은 모두 특정한 크기의 장애물을 필요로 한다. 필요한 장애물의 개수를 최소로 하는 프로그램을 작성하시오. 만약 그러한 경우가 여러개라면 장애물의 크기의 합이 최소가 되는것을 선택한다. 필요한 장애물의 크기의 합을 출력하면 된다.

입력

첫째 줄에 N과 M가 주어진다. N과 M은 50보다 작거나 같고, 3보다 크거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 마지막 줄에는 26개의 숫자가 주어지는데, 첫번째 숫자는 A지형에 필요한 장애물의 크기, 두번째 숫자는 B지형에 필요한 장애물의 크기, ...와 같다.

수도는 한 개만 존재하며, 처음 또는 마지막 열/행에 존재하지 않는다. 또, 장애물의 크기는 1 이상 1,000,000 이하이다.

출력

첫째 줄에 임한수가 설치한 장애물의 크기의 합을 출력한다.

예제 입력

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
3 7
-A-----
-BCCC*-
-A-----
1 5 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

예제 출력

5
5

힌트

출처