경찰과 도둑

덴뷰 제일은행이 막 강탈당했다! 도둑들이 주를 떠나기 전에 붙잡아야 한다.

칼리라도 주는 n행 m열의 직사각형 격자로 나타낼 수 있고, 각 칸의 문자는 지형 종류를 뜻한다. 도둑들은 덴뷰 은행을 나타내는 ‘B’ 칸에서 출발하며, 상하좌우 네 방향으로 인접한 칸으로 이동해 주를 가로지른다. (도둑들은 변을 통해서만 지나가고 모서리는 지나가지 않는다.) 도둑들이 주를 벗어나면(격자의 경계 변을 넘으면) 숨어 버려 다시는 볼 수 없게 된다. 이것을 막아야 한다.

도둑을 잡기 위해 바리케이드를 세울 수 있다. 바리케이드는 칸 안에 설치하며, 어느 방향에서든 도둑이 그 칸으로 들어오지 못하게 막는다. 칸마다 지형이 달라 바리케이드를 세우는 비용이 다르다. 은행(‘B’) 칸과 점(‘.’)이 있는 칸에는 바리케이드를 세울 수 없지만, 도둑들은 이런 칸을 자유롭게 지나다닐 수 있다. 나머지 칸에는 지형 종류를 나타내는 알파벳 소문자가 들어 있다.

도둑들이 칼리라도를 탈출하지 못하게 막는 가장 싼 방법을 구하라.

첫 줄에 세 정수 n, m, c가 주어진다 (1 ≤ n, m ≤ 30, 1 ≤ c ≤ 26). 이는 칼리라도를 나타내는 격자의 크기와 지형 종류의 수이다. 그다음에 정확히 n개의 문자로 이루어진 줄이 m개 주어지며, 이는 칼리라도의 지도이다. 각 문자는 ‘B’, ‘.’ 또는 알파벳 소문자 처음 c개 중 하나이다. 칼리라도에는 은행이 정확히 하나 있음이 보장된다. 격자 다음에는 c개의 정수가 공백으로 구분되어 주어지며, 각 값은 1 ≤ ci ≤ 100 000이다. 이는 각 지형 종류의 칸에 바리케이드를 세우는 비용이다. c1은 지형 ‘a’의 비용, c2는 ‘b’의 비용인 식이다.

도둑들이 탈출하지 못하게 막기 위해 세워야 하는 바리케이드의 최소 총비용을 정수 하나로 출력한다. 도둑들의 탈출을 막을 방법이 없으면 -1을 출력한다.

첫 번째 예제에서 최소 비용은 은행의 각 변에 있는 가운데 세 칸을 막는 것이며, 총비용은 12이다.

두 번째 예제에서는 은행이 경계에 있으므로 도둑들이 주를 탈출하지 못하게 막을 방법이 없다.

세 번째 예제에서는 도둑들이 은행에서 위, 아래, 오른쪽으로 나가지 못하게 막아야 하며, 그렇지 않으면 주를 떠나는 것을 막을 수 없다. 하지만 왼쪽으로는 ‘b’ 칸을 지나가게 두고 그곳에서 세 방향을 각각 막는 편이 더 싸다. 총비용은 7+ 5+ 7+ 3(1) = 22이다.