Среди программистов распространился новый вирус «CodeVid-23». Рудольфу, как программисту, также не удалось избежать его.
Всего есть \(n\) симптомов, пронумерованных от \(1\) до \(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\) — описание симптомов, которые оно снимает, а также описание побочных эффектов.
В первой из строк \(1\) на \(i\)-й позиции означает, что лекарство снимает \(i\)-й симптом, и \(0\) иначе.
Во второй из строк \(1\) на \(i\)-й позиции означает, что после приема появляется \(i\)-й симптом, и \(0\) иначе.
Разные лекарства могут иметь одинаковые наборы симптомов и побочных эффектов. Если лекарство снимает некоторый симптом, то его не будет среди побочных эффектов.
Сумма \(m\) по всем наборам входных данных не превосходит \(10^3\).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите одно целое число — минимальное количество дней, через которое Рудольф сможет избавиться ото всех симптомов. Если этого не случится никогда выведите \(-1\).
Примечание
В первом примере мы можем применить сначала лекарство номер \(4\), после него симптомы примут вид «00101». После этого лекарство номер \(2\), тогда симптомы полностью исчезнут, а количество дней будет равно \(5 + 3 = 8\). Ещё один вариант применения лекарств в порядке \(1, 3, 2\). В этом случае все симптомы также исчезнут, но количество дней будет равно \(3 + 3 + 3 = 9\).
Во втором примере симптомов нет изначально, поэтому лечение займет \(0\) дней.
В третьем примере нет вариантов полностью убрать симптомы.
Примеры
| № | Входные данные | Выходные данные |
|
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
|