8087: BZOJ4087：[Sdoi2015]模拟电路

一家著名的芯片公司希望您能帮他们在一些最新的产品上安装可以稳定电压的组件。每块芯片都被设计成 N×M 的 带插槽的正方形，一个插槽可以安装一块单独的组件，你的任务是尽可能多地插入这些组件。 现代处理器的设计是很复杂的。为了可以稳定电压，你要面对下面几个限制： 一些插槽是不可用的。 一些插槽已经被其它的组件占据了，因而无法被新的组件使用。 内存总线要连接到芯片的水平和垂直的边界上，它们的负载电压需要是安全的。具体来说，芯片公司提供了 N 组 限制条件，分别对应了 N 行。其中对于第 i 行以及第 i 组限制条件，给定非负整数 Ti 与 Ti 个列编号，记为r ij（1≤j≤Ti），要求满足：第 i 行的组件数目不能超过指定的 Ti 个列方向上组件数目的和（也就是不超过“ 第 ri1 列的组件数目 + 第 ri2 列的组件数目 + …”）。为了避免插槽过热，给定浮点数 si（1≤i≤N） 且 0 ≤Si≤1，要求第 i 行的组件数不超过总组件数的 si 。同样给定浮点数 ti（1≤i≤N）且 0≤Ti≤1，要求第 i  列的组件数不超过总组件数的 ti。需要注意的是，已经占据了位置的组件，在统计一行或一列组件总数时，也是 要被考虑在内的。而在计算芯片总组件数时．也要将已经占据了位置的组件考虑进去。芯片被描述为一个 N 行， 每行 N 个字符的矩阵，其中 '.' 表示开放插槽， '/' 表示不可用插槽， 'C' 表示插槽已被一个组件占据。

输入格式

第一行给定 1 个正整数，表示芯片的规模 N（1≤N≤40）。 然后给出 N 行，每行 N 个字符描述插槽，字符为 '.' ， '/' 或 'C' 之一，含义如上所述。 之后 N 行，描述了限制条件。其中第 i 行首先给出非负整数 Ti，表示第 i 行的限制条件涉及到的列的个数。之 后再给出 Ti 个不重复的整数（都在 1 到 N 的范围中），描述了相关的列。 再下一行，给出了 N 个浮点数依次对应 Si，（1≤i≤N）。每一个数字小数点后不超过三位。 再下一行，给出了 N 个浮点数依次对应 ti，（1≤i≤N）。每一个数字小数点后不超过三位。 1≤N≤40

输出格式

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

样例输入

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

样例输出

7
//对于样例1来说，每行每列上的组件不可以超过组件总数的 3/10 ，那么这块 5×5 的芯片的可被安装的最大组件
数是 7 。下图给出的是一种可行方案，其中 'W' 表示新加到开放插槽中的组件。
CC/W．
W/W//
W.C.C
/.CWW
/W/C/

提示

没有写明提示

题目来源

没有写明来源