310528: CF1846G. Rudolf and CodeVid-23

G. Rudolf and CodeVid-23time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

A new virus called "CodeVid-23" has spread among programmers. Rudolf, being a programmer, was not able to avoid it.

There are $n$ symptoms numbered from $1$ to $n$ that can appear when infected. Initially, Rudolf has some of them. He went to the pharmacy and bought $m$ medicines.

For each medicine, the number of days it needs to be taken is known, and the set of symptoms it removes. Unfortunately, medicines often have side effects. Therefore, for each medicine, the set of symptoms that appear when taking it is also known.

After reading the instructions, Rudolf realized that taking more than one medicine at a time is very unhealthy.

Rudolph wants to be healed as soon as possible. Therefore, he asks you to calculate the minimum number of days to remove all symptoms, or to say that it is impossible.

Input

The first line contains a single integer $t$ $(1 \le t \le 100)$ — the number of test cases.

Then follow the descriptions of the test cases.

The first line of each test case contains two integers $n, m$ $(1 \le n \le 10, 1 \le m \le 10^3)$ — the number of symptoms and medicines, respectively.

The second line of each test case contains a string of length $n$ consisting of the characters $0$ and $1$ — the description of Rudolf's symptoms. If the $i$-th character of the string is $1$, Rudolf has the $i$-th symptom, otherwise he does not.

Then follow $3 \cdot m$ lines — the description of the medicines.

The first line of each medicine description contains an integer $d$ $(1 \le d \le 10^3)$ — the number of days the medicine needs to be taken.

The next two lines of the medicine description contain two strings of length $n$, consisting of the characters $0$ and $1$ — the description of the symptoms it removes and the description of the side effects.

In the first of the two lines, $1$ at position $i$ means that the medicine removes the $i$-th symptom, and $0$ otherwise.

In the second of the two lines, $1$ at position $i$ means that the $i$-th symptom appears after taking the medicine, and $0$ otherwise.

Different medicines can have the same sets of symptoms and side effects. If a medicine relieves a certain symptom, it will not be among the side effects.

The sum of $m$ over all test cases does not exceed $10^3$.

Output

For each test case, output a single integer on a separate line — the minimum number of days it will take Rudolf to remove all symptoms. If this never happens, output $-1$.

ExampleInput

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

Output

8
0
-1
6

Note

In the first example, we can first apply medicine number $4$, after which the symptoms will look like "00101". After that, medicine number $2$, then all symptoms will disappear, and the number of days will be $5 + 3 = 8$. Another option is to apply the medicines in the order $1, 3, 2$. In this case, all symptoms will also disappear, but the number of days will be $3 + 3 + 3 = 9$.

In the second example, there are no symptoms initially, so the treatment will take $0$ days.

In the third example, there are no options to remove all symptoms.

**题目大意：**

一个名为 "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 \times m $ 行——药物的描述。

每种药物描述的第一行包含一个整数 $ d $（$ 1 \le d \le 10^3 $）——药物需要服用的天数。

接下来两行是长度为 $ n $ 的由字符 '0' 和 '1' 组成的字符串——药物消除的症状描述和副作用的描述。

在第一行中，位置 $ i $ 上的 '1' 表示药物消除第 $ i $ 个症状，否则为 '0'。

在第二行中，位置 $ i $ 上的 '1' 表示服用药物后出现第 $ i $ 个症状，否则为 '0'。

不同的药物可能有相同的症状和副作用集合。如果一种药物缓解了某个症状，它不会成为副作用。

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

**输出数据格式：**

对于每个测试用例，输出一行，包含一个整数——Rudolf 消除所有症状所需的最少天数。如果不可能，输出 -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
```

**注意：**

在第一个例子中，我们可以首先使用第 4 种药物，之后症状将变为 "00101"。然后使用第 2 种药物，然后所有症状都会消失，需要的天数是 $ 5 + 3 = 8 $ 天。另一种选择是按照 $ 1, 3, 2 $ 的顺序使用药物。在这种情况下，所有症状也会消失，但需要的天数是 $ 3 + 3 + 3 = 9 $ 天。

在第二个例子中，最初没有症状，所以治疗需要 0 天。

在第三个例子中，没有消除所有症状的选项。**题目大意：** 一个名为 "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 \times m $ 行——药物的描述。 每种药物描述的第一行包含一个整数 $ d $（$ 1 \le d \le 10^3 $）——药物需要服用的天数。 接下来两行是长度为 $ n $ 的由字符 '0' 和 '1' 组成的字符串——药物消除的症状描述和副作用的描述。 在第一行中，位置 $ i $ 上的 '1' 表示药物消除第 $ i $ 个症状，否则为 '0'。 在第二行中，位置 $ i $ 上的 '1' 表示服用药物后出现第 $ i $ 个症状，否则为 '0'。 不同的药物可能有相同的症状和副作用集合。如果一种药物缓解了某个症状，它不会成为副作用。 所有测试用例的 $ m $ 之和不超过 $ 10^3 $。 **输出数据格式：** 对于每个测试用例，输出一行，包含一个整数——Rudolf 消除所有症状所需的最少天数。如果不可能，输出 -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 ``` **注意：** 在第一个例子中，我们可以首先使用第 4 种药物，之后症状将变为 "00101"。然后使用第 2 种药物，然后所有症状都会消失，需要的天数是 $ 5 + 3 = 8 $ 天。另一种选择是按照 $ 1, 3, 2 $ 的顺序使用药物。在这种情况下，所有症状也会消失，但需要的天数是 $ 3 + 3 + 3 = 9 $ 天。 在第二个例子中，最初没有症状，所以治疗需要 0 天。 在第三个例子中，没有消除所有症状的选项。