Задача з мікропроцесором
Відома компанія з виробництва мікропроцесорів попросила Вас розмістити декілька компонентів, які можуть взаємно замінюватись, (віджетів) на комп'ютерних чіпах. Кожен чіп складаєьтся з N×N квадратних слотів. Один слот може містити лише один компонент. Вам потрібно розмістити на чіпі якомога більшу кількість віджетів.
Конструкція сучасних процесорів досить складна. На жаль, у Вас є наступні обмеження:
Деякі слоти стали непридатними і не працюють.
Деякі слоти вже містять інші компоненти і не можуть використовуватись для віджетів.
До вертикальних та горизонтальних кінців чіпа пприкріплено шини пам'яті, тому повинна бути врахована їхня пропускна здатність. Саме тому у першому рядку і у першому стовбці повинна знаходитись однакова кількість компонен, число компонент у другому рядку і другому стовбці також повинно співпадати і так далі. При підрахунку компонет слід враховувати як ті, які знаходились на чіпі спочатку, так і віджети, які було додано у пусті слоти.
До кінців кожного рядка і стовбця чіпа підключено джерело живлення. Для уникнення перегріву кожен рядок і стовбець чіпа повинен містити не більше A/B компонент для заданих значень A та B.
Чіп задається N рядками по N символів кожен, де '.' вказує на пустои слот, '/' вказує на пошкоджений слот, а 'C' вказує на те що слот вже зайнято компонентою. Наприклад:
CC/.. ./.// ..C.C /.C.. /./C/
Якщо не більше ніж 3/10 компонент може знаходитсь у кожному рядку і кожному стовбці, то найбільша кількість віджетів яка може бути додана до 5×5 чіпа, становить 7. Можливе розміщення подано нижче, де через 'W' позначено віджет, який додано у відкритий слот.
CC/W. W/W// W.C.C /.CWW /W/C/
Вхідні дані
Вхідні дані складаються з декількох тестів. Кожен тест починається со рядком, який містить три цілих числа: розмір чіпу N (1 ≤ N ≤ 10), і значення A та B (1 ≤ B ≤ 1000, 0 ≤ A ≤ B). Кожен з наступних N рядків містить N символів, які описують слоти: '.', '/' або 'C'.
Останній тест завершується рядком, що містить три нулі.
Вихідні дані
Для кожного тесту у окремому рядку виведіть його номер. Якщо розв'язок існує, то слід вивести максимальну кількість віджетів, які можна розмістити на чіпі. Вивести "impossible", якщо розв'язку не існує.