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

输入数据第1 行有2 个正整数n 和m，n 表示错误总数，m表示补丁总数，1<=n<=20, 1<=m<=100。接下来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。