칩 설계

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

최근의 프로세서 디자인들은 매우 복잡하기 때문에 당신은 운 나쁘게도 아래와 같은 제한들을 지켜야 한다.

• 어떤 슬롯들은 사용할 수 없다.
• 어떤 슬롯들은 다른 부품에 의해 이미 사용되고 있는 중이라서 새로운 위젯을 끼울 수 없다.
• 칩의 수평한 변과 수직한 변을 연결하는 형제 메모리 버스가 있기 때문에 그들의 대역폭을 같게 만들어야 한다. 그러기 위해서는 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 ≤ N ≤ 40), 그리고 위에서 설명한 비율을 의미하는 A와 B(1 ≤ B ≤ 1000, 0 ≤ A ≤ B). 그리고 다음 N개의 줄은 슬롯의 상태를 나타내며 각 줄마다 N개의 문자가 주어진다. 각 문자는 '.','/' 또는 'C'이며 이는 위에서 설명한 대로이다.

마지막 테스트 케이스는 0 세 개로 이루어져 있다.

각 테스트 케이스에 대해 각 줄은 테스트 케이스의 숫자로 시작한다. 만약 가능한 위젯 배치가 있다면 칩 위에 추가할 수 있는 위젯의 최대 개수를 출력한다. 가능한 배치가 없다면 "impossible"을 출력하면 된다.

예제 출력을 따라서 하면 된다.