P2761 Software Patch Problem

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.

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 the minimum total time after the program finishes. If there is no solution, output `0`.

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