Description

Company T discovered that there are $n$ bugs in one of its software products and then released $m$ patch programs for it.

Each patch has its specific applicable environment: a patch can be used only when the software contains certain bugs and at the same time does not contain some other bugs. While removing some bugs, a patch may also introduce new bugs.

In other words, for any patch $i$, there are four associated sets $B1_i,B2_i,F1_i$ and $F2_i$. Patch $i$ can be applied only if the software contains all bugs in $B1_i$ and contains none of the bugs in $B2_i$. Patch $i$ will fix the set of bugs $F1_i$, and at the same time introduce the set of bugs $F2_i$. In addition, running each patch takes a certain amount of time.

Design an algorithm to use the $m$ patch programs provided by Company T to repair the original software into a bug-free state, while minimizing the total time. For the given $n$ bugs and $m$ patches, find a repair plan with the minimum total time.

Input Format

The first line contains two positive integers $n$ and $m$. Here, $n$ is the total number of bugs, and $m$ is the total number of patches.

The next $m$ lines describe the $m$ patches. Each line contains a positive integer representing the time required to run patch $i$, followed by two strings of length $n$, separated by a space character.

In the first string, if the $k$-th character is +, then the $k$-th bug belongs to $B1_i$. If it is -, then the $k$-th bug belongs to $B2_i$. If it is 0, then the $k$-th bug belongs to neither $B1_i$ nor $B2_i$, i.e., whether the software contains the $k$-th bug does not affect the applicability of patch $i$.

In the second string, if the $k$-th character is -, then the $k$-th bug belongs to $F1_i$. If it is +, then the $k$-th bug belongs to $F2_i$. If it is 0, then the $k$-th bug belongs to neither $F1_i$ nor $F2_i$, i.e., whether the software contains the $k$-th bug will not change after applying patch $i$.

Output Format

Output the minimum total time after the program finishes. If there is no solution, output 0.

3 3
1 000 00-
1 00- 0-+
2 0-- -++

8

Hint

Constraints: For $100\%$ of the testdata: $1 \le n \le 20$, $1 \le m \le 100$.

Translated by ChatGPT 5