Sparing w Programowaniu Politechnika Poznańska, 24.02.2007

Opis

To dość zaskakujące i intrygujące, że klienci kupujący nowe oprogramowanie nie oczekują, że będzie ono wolne od błędów. Czy wyobrażasz sobie zakup (nowego) samochodu, którego kierownica pozwala wyłącznie na skręcanie w lewo? A może odtwarzacz CD, który pozwala na odtwarzanie jedynie Hip-Hopu? Pewnie nie. Jednak dla oprogramowania fakt, że nie działa ono tak jak powinno wydaje się akceptowalny. Wiele firm programistycznych powszechnie stosuje praktykę wysyłania łatek na oprogramowanie co kilka tygodni po nowym wydaniu (a niekiedy nawet pobierają za to opłaty).

Tinyware Inc. jest jedną z takich firm. Od wydania nowego edytora tekstów (zeszłego lata) tworzą wciąż nowe łatki. Pod koniec tego tygodnia spostrzegli nowy problem z wydanymi łatkami. O ile każda łatka poprawia jakieś usterki, często instalacja takich poprawek wykorzystuje istnienie innej usterki w systemie, przez co wymusza się jej istnienie.

Formalnie sprawa wygląda następująco. Tinyware znalazło n usterek w swoim oprogramowaniu, B = { b1, b2, ..., bn }. I wydano m łatek p1, p2, ..., pm. W celu zainstalowania łatki pi w oprogramowaniu muszą występować usterki ze zbioru Bi+ (będącego podzbiorem B), natomiast nie mogą już znajdować się tam usterki ze zbioru Bi- (podzbiór B), oczywiście Bi+ oraz Bi- nie mają wspólnych elementów. Łatka naprawia błędy Fi- jeżeli jeszcze nie były one naprawione i wprowadza kolejne Fi+. (Ponownie Fi- oraz Fi+ są rozłączne).

Problem Tinyware jest dość prosty. Zakładając, że posiadamy oryginalną wersję oprogramowania, która zawiera wszystkie usterki ze zbioru B, czy istnieje możliwość zaaplikowania łatek, która pozwoli na uzyskanie oprogramowania bez żadnej znanej usterki? Dalej, jeżeli jest to możliwe, zakładając, że każda łatka potrzebuje określonego czasu na instalację, ile czasu zajmie najkrótsza sekwencja kompletnie łatająca system?

Specyfikacja wejścia

W pierwszej linii wejścia podana będzie liczba d (1 ≤ d ≤ 50) określająca liczbę produktów.

W pierwszej linii opisu każdego produktu znajdują się dwie liczby n (1 ≤ n ≤ 20) i m (1 ≤ m ≤ 100) będące odpowiednio liczbą usterek i patchy. Następnie znajduję się m linii opisujących m łatek. Opis łatki składa się z liczby t (czas instalacji danej łatki, 1 ≤ t ≤ 20*10⁴) oraz dwóch łańcuchów znaków o długości n. Dopuszczalne znaki to '+', '-' oraz '0'. W obu łańcuchach i-ta pozycja odnosi się do i-tej usterki.

W pierwszym łańcuchu '-' oznacza, że dana usterka musi być usunięta w celu instalacji tej łaty, '+' oznacza, że musi być obecna, natomiast '0' wskazuje, że jej obecność nie jest istotna.

W drugim łańcuchu '-' oznacza, że dana łatka usuwa daną usterkę, '+' oznacza, że dana usterka jest wprowadzana do oprogramowania, natomiast '0', że stan usterki pozostawiany jest bez zmian.

Specyfikacja wyjścia

Dla każdego produktu należy wypisać minimalną liczbę sekund potrzebną do usunięcia wszystkich błędów lub -1 w przypadku kiedy usunięcie wszystkich błędów jest niemożliwe.

Przykład

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

8
-1