버그가 아니라 기능입니다!

새 소프트웨어를 구매하는 소비자들이 대체로 그 소프트웨어에 버그가 하나도 없기를 기대하지는 않는다는 것은 흥미로운 사실입니다. 오른쪽으로만 돌아가는 핸들이 달린 자동차를 사겠습니까? 컨트리 음악이 담긴 CD만 재생하는 CD 플레이어는요? 아마 아닐 것입니다. 그런데 소프트웨어는 제대로 동작하지 않아도 어느 정도 용인되는 듯합니다. 실제로 많은 소프트웨어 회사가 신제품 출시 후 몇 주마다 버그를 고치는 패치를 내보내는 (심지어 패치에 돈을 받는) 관행을 갖고 있습니다.

Tinyware Inc. 도 그런 회사 중 하나입니다. 올여름 새 워드 프로세서를 출시한 뒤로 계속 패치를 만들어 왔는데, 이번 주말에야 패치들에 큰 문제가 있다는 것을 깨달았습니다. 모든 패치는 어떤 버그를 고치지만, 설치되기 위해 또 다른 버그가 존재해야 하는 경우가 많습니다. 하나의 버그를 고치기 위해 다른 버그로 인한 특수한 동작을 이용하기 때문입니다.

좀 더 형식적으로 정리하면 다음과 같습니다. 소프트웨어에는 $n$개의 버그 $B = {b_1, b_2, \ldots, b_n}$ 가 있고, $m$개의 패치 $p_1, p_2, \ldots, p_m$ 이 있습니다. 패치 $p_i$ 를 적용하려면 버그 집합 $B_i^+ \subseteq B$ 가 모두 존재해야 하고, 버그 집합 $B_i^- \subseteq B$ 는 모두 존재하지 않아야 합니다 (물론 $B_i^+ \cap B_i^- = \varnothing$). 패치를 적용하면 (존재하던) 버그 $F_i^- \subseteq B$ 가 제거되고, 새로운 버그 $F_i^+ \subseteq B$ 가 추가됩니다 (역시 $F_i^- \cap F_i^+ = \varnothing$).

모든 버그 $B$ 를 포함한 최초 버전에서 시작하여, 패치들을 차례로 적용해 버그가 하나도 없는 버전을 만들 수 있을까요? 만들 수 있다면, 각 패치를 적용하는 데 걸리는 시간이 주어질 때 가장 빠른 순서는 몇 초가 걸릴까요?

입력에는 여러 개의 제품 설명이 들어 있습니다. 각 설명의 첫 줄에는 두 정수 $n$ 과 $m$ 이 주어지며, 각각 버그의 수와 패치의 수입니다 ($1 \le n \le 20$, $1 \le m \le 100$). 그 다음 $m$개의 줄에 패치가 순서대로 주어집니다. 각 줄에는 정수 하나(패치를 적용하는 데 걸리는 시간, 초 단위)와 길이가 $n$인 문자열 두 개가 주어집니다.

첫 번째 문자열은 패치를 적용하기 위한 전제 조건입니다. $i$번째 문자가 +이면 버그 $b_i$ 가 존재해야 하고, -이면 존재하지 않아야 하며, 0이면 존재 여부와 무관합니다.

두 번째 문자열은 패치의 효과입니다. $i$번째 문자가 +이면 버그 $b_i$ 가 새로 추가되고, -이면 (존재할 경우) 제거되며, 0이면 버그 $b_i$ 는 그대로 유지됩니다 (있었다면 그대로 있고, 없었다면 그대로 없습니다).

입력의 끝은 첫 줄이 0 0인 설명으로 표시되며, 이 설명은 처리하지 않습니다.

각 제품 설명에 대해 먼저 Product X 를 출력합니다. 여기서 X 는 제품 번호이며 1부터 시작합니다. 그다음, 모든 버그가 존재하는 제품에서 $n$개의 버그를 모두 제거하는 패치 순서(같은 패치를 여러 번 사용할 수 있음)가 존재하면 Fastest sequence takes S seconds. 를 출력합니다. 여기서 $S$ 는 필요한 최소 총 시간입니다. 그런 순서가 없으면 Bugs cannot be fixed. 를 출력합니다.

연속한 두 제품의 출력 사이에는 빈 줄을 하나 넣습니다.