CF1846G.Rudolf and CodeVid-23

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.

一种名为“CodeVid-23”的新型病毒已在程序员群体中传播。鲁道夫作为一名程序员，也未能幸免。

共有 $n$ 种症状，编号从 $1$ 到 $n$，感染后可能出现其中若干种。初始时，鲁道夫已具有其中一部分症状。他前往药店购买了 $m$ 种药物。

对于每种药物，已知其需连续服用的天数，以及它能消除的症状集合。不幸的是，药物常伴有副作用，因此对每种药物，还已知其在服用期间会引发的症状集合。

阅读说明书后，鲁道夫意识到同时服用多种药物极不健康。

鲁道夫希望尽快康复。因此，他请你计算清除所有症状所需的最少天数；若不可能清除所有症状，则输出相应说明。

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$.

第一行包含一个整数 $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$。

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$.

对于每个测试用例，在单独一行输出一个整数——鲁道夫清除所有症状所需的最少天数。如果这种情况永远不会发生，则输出 $-1$。

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.

在第一个例子中，我们可以先使用药品 4，之后症状将变为 "00101"；接着使用药品 2，所有症状便会全部消失，总耗时为 $5 + 3 = 8$ 天。另一种方案是按顺序使用药品 $1, 3, 2$，此时所有症状同样会消失，但总耗时为 $3 + 3 + 3 = 9$ 天。

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

在第三个例子中，不存在能清除所有症状的方案。