Kapitan Mambeks buduje bombę xpolimerową. Cząstki xpolimeru zbudowane są z łańcuchów alfa i beta glutyny. Typ xpolimeru jest zwyczajowo zapisywany za pomocą ciągu liter a i b. Cząstki xpolimeru nie są symetryczne - xpolimery aabb i bbaa to dwa różne typy xpolimeru. Xpolimery mają silne właściwości wybuchowe. Zetknięcie się łańcucha xpolimeru z łańcuchem polimeru dłuższym o jedną cząstkę powoduje inicjacje reakcji łańcuchowej i wybuch xpolimerów. Przykładowo zetknięcie się par polimerów (aabba, aabb) lub (bbaab, bbaa) powoduje wybuch, natomiast parę polimerów (aabbbb, abbb) można bezpiecznie wymieszać. Kapitan Mambeks posiada zapasy xpolimerów różnych typów. Zapasy te są zgromadzone w beczkach o różnej masie. Kapitan posiada także generator xpolimerów, który może wyprodukować małe ilości xpolimeru dowolnego typu. Kapitan chce zbudować bardzo dużą bombę. W tym celu musi wymieszać zapasy xpolimerów z beczek. Detonator bomby zostanie stworzony z xpolimerów wytworzonych przez generator polimerów. Napisz program, który wyznaczy maksymalną masę bomby. Pamiętaj, że w mieszaninie polimerów nie może się znaleźć para polimerów powodujących eksplozję.
Dane wejściowe:
W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych n, n >= 0 i n <= 20. W kolejnych wierszach jest zapisanych n zestawów danych wejściowych. W pierwszym wierszu zestawu znajduje się liczba całkowita k - liczba beczek xpolimeru, k <= 1000. W kolejnych k liniach znajdują się opisy beczek. Opis beczki składa się z typu xpolimeru - ciągu liter a i b, oraz liczby całkowitej m oznaczającej masę beczki. Typ polimeru i masa beczki są oddzielone spacją. Maksymalna długość xpolimeru wynosi 120 cząstek. Maksymalna masa beczki wynosi 150. Masa pustej beczki jest znikoma w porównaniu do masy xpolimeru w niej składowanej.
Dane wyjściowe:
Dla każdego zestawu danych wejściowych program powinien wypisać jeden wiersz odpowiedzi zawierający maksymalną masę bomby, którą może zbudować kapitan.
Przykładowe dane wejściowe:
1
6
aa 2
aab 2
aaa 1
aaaa 3
b 3
bb 10
Przykładowe dane wyjściowe:
15