3659: 软件补丁

T 公司发现其研制的一个软件中有n 个错误，随即为该软件发放了一批共m 个补丁程序。
每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不
包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。
换句话说，对于每一个补丁i，都有2 个与之相应的错误集合B1[i]和B2[i]，使得仅当软件包
含B1[i]中的所有错误，而不包含B2[i]中的任何错误时，才可以使用补丁i。补丁i 将修复软
件中的某些错误F1[i]，而同时加入另一些错误F2[i]。另外，每个补丁都耗费一定的时间。
试设计一个算法，利用T 公司提供的m 个补丁程序将原软件修复成一个没有错误的软件，
并使修复后的软件耗时最少。
对于给定的n 个错误和m 个补丁程序，找到总耗时最少的软件修复方案。

第1 行有2 个正整数n 和m，n 表示错误总数，m 表
示补丁总数。接下来m 行给出了m 个补丁的信息。每行包括一个正整数，表示运行补丁
程序i 所需时间，以及2 个长度为n 的字符串，中间用一个空格符隔开。第1 个字符串中，
如果第k 个字符bk 为“+”，则表示第k 个错误属于B1[i]，若为“-”， 则表示第k 个错误
属于B21[i]，若为“0”，则第k 个错误既不属于B1[i]也不属于B2[i]，即软件中是否包含第
k 个错误并不影响补丁i 的可用性。第2 个字符串中，如果第k 个字符bk 为“-”，则表示
第k 个错误属于F1[i]，若为“+”，则表示第k 个错误属于F2[i]，若为“0”， 则第k 个错
误既不属于F1[i]也不属于F2[i]，即软件中是否包含第k 个错误不会因使用补丁i 而改变。

总耗时。如果问题无解，则输出0。

3 3
1 000 00-
1 00- 0-+
2 0-- -++

8