一个程序总有个错误，公司经常发布补丁来修正这些错误，遗憾的是，每用一个补丁，在修正某些错误的时候，同时会加入某些错误，每个补丁都有一定运行时间。 某公司发表了一个游戏，出现了n个错误B={b1,b2,b3,……bn}，于是该公司发布了m个补丁，每个补丁的应用都是有条件的（即哪些错误必须存在，哪些错误不能存在）。 求最少需要多少时间可全部修正这些错误。

第一行有两个正整数n和m，n表示错误总数，m表示补丁总数(1<=n<=20,1<=m<=100)。接下来m行给出了m个补丁的信息。每行包括一个正整数（表示此补丁程序的运行时间）和两个字符串，第一个字符串描述了应用该补丁的条件。字符串的第i个字符，如果是‘+’，表示在软件中必须存在第bi号错误；如果是‘-’，表示软件中错误bi不能存在；如果是‘0’，则表示错误bi存在或不存在均可（即对应用该补丁没用影响）。 第二个字符串描述了应用该补丁的效果。字符串的第i个，如果是‘+’，表示产生了一个新错误bi；如果是‘-’，表示错误bi被修改好了；如果是‘0’，则表示错误bi不变（即原来存在的，仍然存在；原来不存在，还是不存在）。

输出一个整数，如果问题有解，输出总耗时。否则输出-1。

3 5
1 0-+ -+-
3 +-- -00
4 000 00-
6 +0+ -0-
3 0+0 0-0

7

样例说明：初始：+++，使用第5条规则，变成+-+，时间为3
                  使用第1条规则，变成-+-,时间为1
                  使用第5条规则，变成---，时间为3
一共需要的时间为7，这是最短时间。