测试数据来自 system/1961

描述

一家著名的芯片公司希望您能帮他们在一些最新的产品上安装可以稳定电压的组件。每块芯片都被设计成\(N\times N\) 的带插槽的正方形，一个插槽可以安装一块单独的组件，你的任务是尽可能多地插入这些组件。

现代处理器的设计是很复杂的。为了可以稳定电压，你要面对下面几个限制：
(1)一些插槽是不可用的。
(2)一些插槽已经被其它的组件占据了，因而无法被新的组件使用。
(3)内存总线要连接到芯片的水平和垂直的边界上，它们的负载电压需要是安全的。具体来说，芯片公司提供了N组限制条件，分别对应了N 行。其中对于第i行以及第i组限制条件，给定非负整数\(T_i\)与\(T_i\)个列编号，记为\(r_{ij}\) （\(1\le j\le T_i\)），要求满足：第i行的组件数目不能超过指定的\(T_i\)个列方向上组件数目的和（也就是不超过“第\(r_{i1}\)列的组件数目＋第\(r_{i2}\) 列的组件数目＋\(\cdots\)”）。
(4)为了避免插槽过热，给定浮点数\(s_i\)（\(1\le i\le N\)）且\(0\le s_i\le 1\)，要求第i行的组件数不超过总组件数的\(s_i\)。 同样给定浮点数\(t_i\) （\(1\le i\le N\)）且\(0\le t_i\le 1\)，要求第i列的组件数不超过总组件数的\(t_i\)。

需要注意的是，已经占据了位置的组件，在统计一行或一列组件总数时，也是要被考虑在内的。而在计算芯片总组件数时，也要将已经占据了位置的组件考虑进去。

芯片被描述为一个N行，每行N个字符的矩阵，其中'.' 表示开放插槽，'/' 表示不可用插槽，'C' 表示插槽已被一个组件占据。

格式

输入格式

第一行给定\(1\)个正整数，表示芯片的规模N（\(1\le N\le 40\)）。

然后给出N行，每行N个字符描述插槽，字符为'.'，'/' 或'C' 之一，含义如上所述。

之后N行，描述了限制条件。其中第i行首先给出非负整数\(T_i\)，表示第i行的限制条件涉及到的列的个数。之后再给出\(T_i\) 个不重复的整数（都在1到N的范围中），描述了相关的列。

再下一行，给出了N个浮点数依次对应\(s_i\)，（\(1\le i\le N\)）。每一个数字小数点后不超过三位。

再下一行，给出了N个浮点数依次对应\(t_i\)，（\(1\le i\le N\)）。每一个数字小数点后不超过三位。

输出格式

如果存在合法的策略，输出最多可以再在芯片上安装多少个组件。否则输出“impossible”（不用输出分号）。

样例1

样例输入1

5
CC/..
././/
..C.C
/.C..
/./C/
1 1
1 2
1 3
1 4
1 5
0.3 0.3 0.3 0.3 0.3
0.3 0.3 0.3 0.3 0.3

样例输出1

7

样例2

样例输入2

5
CC/..
././/
..C.C
/.C..
/./C/
1 1
1 2
1 3
1 4
1 5
0.2 0.2 0.2 0.2 0.2
0.2 0.2 0.2 0.2 0.2

样例输出2

impossible

限制

对于5%的数据，\(1\le N\le 4\)。

存在45%的数据，\(T_i\)恒为0。其中更有15%的数据，不存在已经占据了位置的组件。

存在20%的数据，\(T_i\)恒为1，且一定有\(r_{i1}=i\)。

对于100%的数据，\(1\le N\le 40\)。

提示

对于样例一来说，每行每列上的组件不可以超过组件总数的\(3/10\)，那么这块\(5\times 5\)的芯片的可被安装的最大组件数是7。

来源

SDOI2015 round2 day2