통신

어린 수학도가 다니는 유치원에서는 서로 소통하는 법도 가르쳐야 한다. 그래서 건물 안의 어떤 두 방이든 컴퓨터 네트워크로 이어져 있어야 한다. 이 문제에서 유치원 건물은 $V$개 층으로 이루어진 직육면체이고, 한 층에는 방이 $R \times S$개 있다. 방을 잇는 비용은 최소여야 한다. 같은 층에서 벽을 맞댄 두 방을 잇는 데는 1000코루나가 들고, 위아래로 맞닿은 두 방, 즉 한 방의 천장이 다른 방의 바닥인 경우를 잇는 데는 2000코루나가 든다. 여기에 이미 이어져 있는 방까지 있어서 계산이 까다롭다. 모든 방을 하나의 네트워크로 잇는 데 필요한 최소 비용을 구하는 프로그램을 작성하라.

선은 벽이나 바닥을 맞댄 이웃한 두 방 사이에만 놓을 수 있고, 선을 여러 개 거쳐 이어진 두 방도 서로 통신한다.

입력은 여러 블록으로 이루어진다. 블록 하나가 건물 하나를 나타낸다. 블록의 첫 줄에는 세 정수 $V$, $R$, $S$가 주어진다 ($1 \le V, R, S \le 63$). 입력의 마지막 블록은 첫 줄이 0 0 0이고, 이 블록은 처리하지 않는다.

첫 줄 다음에는 1층 배치도, 1층과 2층 사이의 연결도, 2층 배치도, 2층과 3층 사이의 연결도가 이 순서로 이어지며 맨 위층 배치도에서 끝난다. 배치도와 연결도 뒤에는 각각 빈 줄이 하나씩 온다.

한 층의 배치도는 $2R-1$개의 줄로 이루어지고, 한 줄에는 문자가 $2S-1$개 있다. 줄과 칸을 1부터 셀 때, 홀수 줄의 홀수 칸에 있는 *는 방을 나타낸다. 한 줄에서 방을 나타내는 두 문자 사이에는 - 또는 .이 온다. -는 두 방이 이미 이어져 있다는 뜻이고, .은 이어져 있지 않다는 뜻이다. 짝수 줄의 짝수 칸은 항상 .이고, 홀수 칸에는 . 또는 |가 온다. |는 그 문자 바로 위와 바로 아래의 *가 나타내는 두 방이 이미 이어져 있다는 뜻이다.

층 사이의 연결도도 $2R-1$개의 줄로 이루어지고, 한 줄에는 문자가 $2S-1$개 있다. 짝수 줄은 모두 .이다. 홀수 줄의 짝수 칸도 .이고, 홀수 칸에는 . 또는 o가 온다. o는 그 위치에 있는 아래층 방과 위층 방이 이미 이어져 있다는 뜻이다.

건물마다 한 줄씩 출력한다. 건물의 모든 방이 이미 하나의 네트워크로 이어져 있으면 다음 줄을 출력한다.

Budova je jiz dostatecne propojena.

그렇지 않으면 다음 줄을 출력한다.

Ocekavana cena: XXXX Kc

XXXX는 모든 방을 잇는 데 필요한 최소 비용이다. 비용은 뒤에서부터 세 자리마다 쉼표를 넣어 적는다. 3000은 3,000, 518000은 518,000으로 적는다.