题目描述

一种名为“CodeVid-23”的新病毒正在程序员中传播。Rudolf 作为一名程序员，也未能幸免。

共有 $n$ 种症状，编号从 $1$ 到 $n$，感染后可能出现。起初，Rudolf 已经有了一些症状。他去药店买了 $m$ 种药。

对于每种药，已知需要服用的天数，以及它能消除的症状集合。不幸的是，药物通常有副作用。因此，对于每种药，还知道服用时会出现的症状集合。

Rudolf 发现，同时服用多种药物非常不健康。

Rudolf 希望尽快痊愈。因此，他请你计算消除所有症状所需的最少天数，或者判断是否无法治愈。

输入格式

第一行包含一个整数 $t$ $(1 \le t \le 100)$，表示测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$ $(1 \le n \le 10, 1 \le m \le 10^3)$，分别表示症状数和药物数。

第二行包含一个长度为 $n$ 的仅由 $0$ 和 $1$ 组成的字符串，描述 Rudolf 当前的症状。如果第 $i$ 个字符为 $1$，则 Rudolf 有第 $i$ 种症状，否则没有。

接下来有 $3 \cdot m$ 行，描述每种药物。

每种药物的第一行包含一个整数 $d$ $(1 \le d \le 10^3)$，表示该药物需要服用的天数。

接下来的两行分别为长度为 $n$ 的仅由 $0$ 和 $1$ 组成的字符串，分别描述该药物能消除的症状和服用后出现的副作用症状。

在第一行中，第 $i$ 位为 $1$ 表示该药物能消除第 $i$ 种症状，否则不能。

在第二行中，第 $i$ 位为 $1$ 表示服用该药物后会出现第 $i$ 种症状，否则不会。

不同的药物可能有相同的消除症状和副作用集合。如果某药物能消除某种症状，则该症状不会出现在副作用中。

所有测试用例中 $m$ 的总和不超过 $10^3$。

输出格式

对于每个测试用例，输出一个整数，表示 Rudolf 消除所有症状所需的最少天数。如果无法消除所有症状，输出 $-1$。

说明/提示

在第一个样例中，可以先使用第 $4$ 种药物，此时症状变为“00101”。然后使用第 $2$ 种药物，所有症状都消失，总天数为 $5+3=8$。另一种方案是依次使用第 $1,3,2$ 种药物，也能消除所有症状，但总天数为 $3+3+3=9$。

在第二个样例中，初始时没有任何症状，因此治疗天数为 $0$。

在第三个样例中，没有办法消除所有症状。

由 ChatGPT 4.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

8
0
-1
6