Runda 26 - Wyścigi Futerkowych Zaprzęgów

Zawody stałe, runda 26

Limit czasowy: 1s; Limit pamięciowy: 32MB

Wyścigi futerkowych zaprzęgów

W odbywających się co co roku Otwartych Bajtockich Mistrzostwach Futerkowych Zaprzęgów biorą udział najlepsi woźnicy z całego świata. Niezaprzeczalnym faworytem zbliżających się zawodów jest Bert Bica wraz ze swoimi sympatycznymi szczurołakami. Gra toczy się o niemałą stawkę - zwycięzca, poza wieczną chwałą, otrzymuje wysokie honorarium, a wszyscy sponsorzy wręcz zabijają się o każdy centymetr na jego koszuli.
Książę Kaspar postanowił przede wszystkim odzyskać reputację po ostatniej porażce, kiedy to jego zaprzęg lemingów niespodziewanie skoczył z urwiska. Dlatego już od jesieni trenuje na ukrytym torze w lesie niedaleko swojej posiadłości. Tym razem postawił na mieszaną hodowlę świstaków - poza rodzimym Bajtockim, sprowadził jeszcze gatunek z Cobolandii.
Futerkowy zaprzęg składa się z K par gryzoni* biegnących w szeregu. Kluczem do sukcesu wydaję się wybranie nie tylko najsprawniejszych osobników, ale również ich odpowiedni rozkład. Okazuje się że dwie pary tego samego gatunku świstaka nie mogą biec bezpośrednio jedna za drugą na jakimkolwiek fragmencie zaprzęgu - inaczej wyraźnie traci on manewrowość na zakrętach. Podobnie ma się sprawa w przypadku czterech świstaków tego samego gatunku biegnących dokładnie jeden za drugim. Za moc zaprzęgu uznaje się zaś sumę sił wszystkich jego świstaków, przy czym pierwsze dziesięć liczy się dwukrotnie (narzucają one bowiem tempo pozostałym).
Książę chciałby wiedzieć, jak silny może być jego zaprzęg jeśli wykluczy te niekorzystne konfiguracje.
Poprosił Cię o pomoc w sprawdzeniu tego, i obiecał, że w razie wygranej podzieli się z Tobą nagrodą pół na pół - dla niego sława, dla Ciebie pieniądze. Taka okazja może się szybko nie powtórzyć!

Wejście:

W pierwszej linii wejścia znajdują się dwie liczby - kolejno ilość świstaków w hodowli i określona w przepisach dokładna wielkość zaprzęgu.
W kolejnych liniach znajdują się pary - siła świstaka oraz jego gatunek ('b' - bajtocki, 'c' - cobolandzki).

Wyjście:

Napis "NIE" jeśli nie da się skonstruować zaprzęgu zgodnie z podanymi kryteriami, lub jedna liczba całkowita - moc najsilniejszego możliwego zaprzęgu.

Test przykładowy:

Wejście:

8 4
2 b
3 b
8 b
6 b
4 c
3 b
2 b
1 b

Wyjście:

NIE

Wejście:

12 5
6 b
4 b
3 b
4 b
5 b
6 b
10 b
1 c
3 b
2 c
11 b
12 b

Wyjście:

122

----
* - obecnie przepisy nie dopuszczają lemingów oraz jeżozwierzy ze względu na drastyczne sceny z ich udziałem w poprzednich mistrzostwach.