U238376 [WF2011] Chips Challenge

有一个芯片，芯片上有 $N\times N$（$1\le N\le 40$）的位置，每一个位置都有插槽，可以在里面装零件。 有些插槽不能装零件，有些插槽必须装零件，剩下的插槽随意。 要求装好之后满足如下两条要求： 1. 第 $i$ 行和第 $i$ 列的零件数目必须一样多（$1\le i\le N$）。 2. 第 $i$ 行的零件数目不能超过总的零件数目的 $\frac{A}{B}$（$1\le i\le N$，$0\le A\le B\le 10^3$，$B\neq 0$）。 求最多可以另外放多少个零件（就是除掉必须放的）。如果无解输出 `impossible`。

输入由一些测试样例组成。每一行都有三个整数，分别是 $N$ 芯片的大小，$A$ 和 $B$。 然后 $N$ 行每一行都有 $N$ 个字符，每一个字符都描述当前位置的插槽。 最后一行输入为 $3$ 个 $0$，请不要处理这一行。

对于每一组测试样例，请先输出 `Case P: ` 的字样，其中 $P$ 代表当前是第 $P$ 组测试样例。 如果当前的输入有一种解决方案，请输出可以添加到芯片的最大部件数量。否则输出 `impossible`。

$1\le N\le 40$。