← 返回题目列表

Codeforces · 1846/G

G. 鲁道夫和 CodeVid-23

中文机器翻译题面 查看原题

一种名为“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$$$ 天。

在第三个示例中,没有用于删除所有症状的选项。