一种名为“CodeVid-23”的新病毒已在程序员中传播。鲁道夫作为一名程序员,无法避免它。
感染后可能会出现从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 症状。最初,鲁道夫拥有其中一些。他去药房买了$$$m$$$ 的药品。
对于每种药物,需要服用的天数以及它消除的症状都是已知的。不幸的是,药物常常有副作用。因此,对于每种药物,服用时出现的一系列症状也是已知的。
读完说明书后,鲁道夫意识到一次服用一种以上的药物是非常不健康的。
鲁道夫希望尽快痊愈。所以他要求你计算一下最少需要多少天才能消除所有症状,或者说不可能。
输入
第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 100)$$$ — 测试用例的数量。
然后按照测试用例的描述进行操作。
每个测试用例的第一行包含两个整数 $$$n, m$$$ $$$(1 \le n \le 10, 1 \le m \le 10^3)$$$ — 分别是症状和药物的数量。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串,由字符 $$$0$$$ 和 $$$1$$$ 组成 - 鲁道夫症状的描述。如果字符串的第 $$$i$$$ 个字符是 $$$1$$$,则鲁道夫有第 $$$i$$$ 个症状,否则他没有。
然后跟随 $$$3 \cdot m$$$ 行 — 药物的描述。
每个药物说明的第一行包含一个整数 $$$d$$$ $$$(1 \le d \le 10^3)$$$ — 药物需要服用的天数。
药物描述的接下来两行包含两个长度为 $$$n$$$ 的字符串,由字符 $$$0$$$ 和 $$$1$$$ 组成 - 其消除的症状的描述和副作用的描述。
在两行的第一行中,位置 $$$i$$$ 处的 $$$1$$$ 表示该药物消除了第 $$$i$$$ 个症状,否则为 $$$0$$$。
两行中的第二行中,$$$i$$$位置处的$$$1$$$表示服药后出现第$$$i$$$症状,否则为$$$0$$$。
不同的药物可能有相同的症状和副作用。如果药物可以缓解某种症状,那么它就不属于副作用。
所有测试用例的 $$$m$$$ 总和不超过 $$$10^3$$$。
输出
对于每个测试用例,在单独的行上输出一个整数 - 鲁道夫消除所有症状所需的最少天数。如果这种情况从未发生,则输出 $$$-1$$$。
示例
输入 #1
4 5 4 10011 3 10000 00110 3 00101 00000 3 01010 00100 5 11010 00100 4 1 0000 10 1011 0100 2 2 11 2 10 01 3 01 10 2 3 11 3 01 10 3 10 00 4 10 01
输出 #1
8 0 -1 6
注意
在第一个例子中,我们可以先使用编号为$$$4$$$的药物,之后症状将类似于“00101”。之后,药物编号$$$2$$$,则所有症状都会消失,天数为$$$5 + 3 = 8$$$。另一种选择是按照 $$$1、3、2$$$ 的顺序使用药物。在这种情况下,所有症状也会消失,但天数将为$$$3 + 3 + 3 = 9$$$。
在第二个示例中,最初没有任何症状,因此治疗将需要 $$$0$$$ 天。
在第三个示例中,没有用于删除所有症状的选项。