칩 설계

유명한 마이크로프로세서 회사 letnI는 컴퓨터 칩 위에 교체 가능한 부품(위젯)을 배치하는 일에 당신의 도움이 필요하다. 각 칩은 $N \times N$개의 정사각형 슬롯으로 이루어져 있다. 한 슬롯에는 위젯을 최대 하나 끼울 수 있으며, 목표는 위젯을 최대한 많이 추가하는 것이다.

최신 칩 설계는 매우 복잡하므로 다음 제한들을 지켜야 한다.

• 어떤 슬롯은 사용할 수 없다.
• 어떤 슬롯은 이미 다른 부품이 차지하고 있어서 새 위젯을 끼울 수 없다.
• 칩의 가로 변과 세로 변을 잇는 형제 메모리 버스가 있으며, 이들의 대역폭이 같아야 한다. 이를 위해 모든 인덱스 $i$에 대해 $i$번째 행에 있는 부품의 개수와 $i$번째 열에 있는 부품의 개수가 같아야 한다. 여기서 부품의 개수는 이미 놓여 있는 부품과 새로 추가한 위젯을 모두 포함한다.
• 각 행과 열의 끝에는 전원 공급 장치가 연결된다. 과열을 막기 위해, 임의의 한 행이나 열에 있는 부품의 개수와 칩 전체에 있는 부품의 총 개수의 비율이 $A / B$를 초과해서는 안 된다($A$와 $B$는 각 칩마다 주어진다).

칩은 각 줄에 $N$개의 문자가 있는 $N$개의 줄로 주어진다. .은 열려 있는(현재 사용되지 않은) 슬롯, /은 사용할 수 없는 슬롯, C는 이미 다른 부품이 차지한 슬롯이다. 예를 들어 다음 칩을 보자.

CC/..
././/
..C.C
/.C..
/./C/

한 행이나 열이 전체 부품의 $3/10$을 초과해서 가질 수 없다고 하면, 이 칩에 추가할 수 있는 위젯의 최대 개수는 $7$이다. 아래는 한 가지 유효한 배치이며, W는 열린 슬롯에 추가한 위젯을 나타낸다.

CC/W.
W/W//
W.C.C
/.CWW
/W/C/

칩이 주어질 때, 추가할 수 있는 위젯의 최대 개수를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스의 첫 줄에는 세 정수, 즉 칩의 크기 $N$ ($1 \le N \le 40$)과 위에서 설명한 비율을 나타내는 $A$, $B$ ($1 \le B \le 1000$, $0 \le A \le B$)가 주어진다. 이어지는 $N$개의 줄은 슬롯의 상태를 나타내며, 각 줄에는 위에서 설명한 대로 ., /, C 중 하나인 문자 $N$개가 주어진다.

마지막 테스트 케이스 다음에는 0 세 개로 이루어진 줄이 온다.

각 테스트 케이스에 대해 한 줄을 출력한다. 유효한 위젯 배치가 존재하면 Case X: k를 출력하는데, 여기서 $X$는 테스트 케이스 번호($1$부터 시작)이고 $k$는 추가할 수 있는 위젯의 최대 개수이다. 유효한 배치가 없으면 Case X: impossible을 출력한다.