题目描述

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

编程任务： 对于给定的$\red{n}$个错误和$\red{m}$个补丁程序，找到总耗时最少的软件修复方案。

输入格式

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

输出格式

程序运行结束时，将总耗时数输出。如果问题无解，则输出$\red{0}$。

样例

输入样例

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

输出样例

8