Description：

给一个正方形网格，有些位置不能放，有些位置必须放，第 $i$ 行和第 $i$ 列放的个数必须一样多，任意一行 $/$ 一列放的个数不能超过总数的 $A/B$ ，问最多能放几个

$1\leqslant n\leqslant 40$

Solution：

显然最不好做的限制是任意一行 $/$ 一列放的个数不超过总数的 $A/B$ ，这个时候有一个很神仙的做法就是我们枚举每一行 $/$ 一列放的个数的最大值 $t$ ，那么有 $t\leqslant A/B\times sum$ ，即 $t\times B\leqslant sum\times A$ ，直接求不好求，我们可以补集转化，先把能放的都放了，然后再把多余的扣掉，然后从源点向代表行的点连 $(cntx[i],0)$ 的边，从代表列的点向汇点连 $(cnty[i],0)$ 的边，对应行和列连 $(t,0)$ 的边，然后从代表行的点向代表列的点连 $(1,1)$ 的边，代表把这个点扣掉，那么我们应该让抠掉的最少，也就是跑最小费用最大流，当且仅当满流时并且 $t\times B\leqslant (t\times n-cost)\times A$ 时合法，更新答案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,A,B;

#define MAXN 50

char map[MAXN][MAXN];

int cntx[MAXN],cnty[MAXN],sum = 0,cntc = 0;

char getc()

{

	register char c = getchar();

	while(c != '.' && c != '/' && c != 'C')c = getchar();

	return c;

}

#define MAXP (MAXN * 2)

#define MAXE (MAXN * MAXN + 3 * MAXN)

struct edge

{

	int to,nxt,f,c;

}e[MAXE << 1];

int edgenum = 0;

int lin[MAXP];

void add(int a,int b,int f,int c)

{

	e[edgenum] = (edge){b,lin[a],f,c};lin[a] = edgenum++;

	e[edgenum] = (edge){a,lin[b],0,-c};lin[b] = edgenum++;

	return;

}

int pre[MAXP],d[MAXP],rate[MAXP];

bool inq[MAXP];

int s,t;

#define INF 0x3f3f3f3f

bool SPFA()

{

	memset(d,0x3f,sizeof(d));d[s] = 0;

	rate[s] = INF;

	queue<int> q;q.push(s);

	while(!q.empty())

	{

		int k = q.front();q.pop();

		inq[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].c && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].c;

				rate[e[i].to] = min(rate[k],e[i].f);

				pre[e[i].to] = i;

				if(!inq[e[i].to])

				{

					inq[e[i].to] = k;

					q.push(e[i].to);

				}

			}

		}

	}

	return d[t] != INF;

}

#define pii pair<int,int>

pii flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	return make_pair(rate[t] * d[t],rate[t]);

}

pii operator + (pii a,pii b){return make_pair(a.first + b.first,a.second + b.second);}

pii EK()

{

	pii ans = make_pair(0,0);

	while(SPFA())ans = ans + flow();

	return ans;

}

int calc(int v)

{//cout << " : " << v << endl;

	memset(lin,-1,sizeof(lin));

	edgenum = 0;

	s = 2 * n + 1;t = s + 1;

	for(int i = 1;i <= n;++i)add(s,i,cntx[i],0);

	for(int i = 1;i <= n;++i)add(i + n,t,cnty[i],0);

	for(int i = 1;i <= n;++i)add(i,i + n,v,0);

	for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)if(map[i][j] == '.')add(i,j + n,1,1);

	pii res = EK();//cout << res.first << " " << res.second << endl;

	if(res.second != sum)return -1;

	if(v * B > (res.second - res.first) * A)return -1;

	return res.second - res.first;

}

int main()

{

	int testcases = 0;

	while(true)

	{

		n = rd();A = rd();B = rd();

		if(n == 0 && A == 0 && B == 0)break;

		for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)map[i][j] = getc();

		memset(cntx,0,sizeof(cntx));

		memset(cnty,0,sizeof(cnty));

		sum = 0;cntc = 0;

		for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)if(map[i][j] != '/')++cntx[i],++cnty[j];

		for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)if(map[i][j] == 'C')++cntc;

		for(int i = 1;i <= n;++i)sum += cntx[i];//cout << " -> " << sum << endl;

		int ans = -1;

		for(int v = 0;v <= n;++v)ans = max(ans,calc(v));

		if(ans == -1)printf("Case %d: impossible\n",++testcases);

		else printf("Case %d: %d\n",++testcases,ans - cntc);

	}

	return 0;

}