Finále

C: Fronta na trička

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Trička s logem expedice Kasiopea jsou i na Ma-stře žádanou komoditou, na kterou se stojí dlouhé fronty hodiny před tím, než se vůbec otevřou přepážky, na kterých si je lze pořídit. Přepážek (a tedy i front) je K a Pali, který právě přišel a také si chce takové tričko pořídit, se rozhoduje, do které z front se zařadí. "To je přece jasné, do té nejkratší!", řekl si. Po chvíli pozorování si ale něčeho povšiml.

Každý člověk, který stojí v některé z front, se dá zařadit do jedné skupiny dle svého temperamentu: je to sangvinik (S), cholerik (C), flegmatik (F), nebo melancholik (M). Když vedle sebe ve frontě stojí dva lidé stejného temperamentu, zapovídají se a přesně po minutě:

  • odejdou na pizzu, jedná-li se o dva sangviniky,
  • poperou se a odejdou, jedná-li se o dva choleriky,
  • rozpláčou se nad délkou fronty a odejdou, jedná-li se o dva melancholiky,
  • uvědomí si, že jim na tričkách vlastně nesejde a odejdou, jedná-li se o dva flegmatiky.

Poté, co po minutě nějací lidé odejdou, se celý proces opakuje znovu. Jestliže je ve frontě za sebou souvislá skupina více než dvou lidí stejného temperamentu, bude si vždy povídat první s druhým, třetí s čtvrtým atd. Poslední si tedy s nikým povídat nebude, je-li délka této skupiny lichá.

Vzhledem k tomu, jak to v Kasiopee chodí s termíny, může Pali předpokládat, že se přepážky s tričky otevřou až dlouho poté, co v žádné frontě vedle sebe nebudou stát dva lidi se stejným temperamentem. Pomozte Palimu zjistit, kolik lidí nakonec bude v nejkratší frontě.

Pali si všiml ještě jednoho pozoruhodného faktu. Posloupnost temperamentů prvních N členů každé fronty je pro všechny fronty stejná.

Vstup

Na první řádce vstupu je přirozené číslo T - počet problémů, které musíte vyřešit. Pro každý problém dostanete na první řádce jedno přirozené číslo K - počet front. Druhá řádka obsahuje jedno přirozené číslo N následované řetězcem obsahujícím N znaků. Tento řetězec reprezentuje temperamenty prvních N lidí v každé frontě.

Následuje k řádek. Každá z nich obsahuje jedno přirozené číslo Ni následované řetězcem obsahujícím Ni znaků. Tento řetězec reprezentuje temperamenty zbylých Ni lidí v i-té frontě. Všechny řetězce včetně prvního obsahují pouze znaky 'S', 'C', 'M', 'F'. Všimni si, že v i-té frontě stojí N+Ni lidí.

Výstup

Na výstup vypiš jediné číslo - délku fronty, ve které nakonec zbude nejméně lidí (takových front může být více).

Lehká verze

  • 1 ≤ T ≤ 10
  • 1 ≤ K ≤ 10
  • 1 ≤ N ≤ 1 000
  • 1 ≤ Ni ≤ 1 000 pro všechna i od 1 do K

Těžká verze

  • 1 ≤ T ≤ 10
  • 1 ≤ K ≤ 1 000 000
  • 1 ≤ N ≤ 1 000 000
  • 1 ≤ Ni ≤ 1 000 000 pro všechna i od 1 do K. Navíc platí N1 + N2 + … + NK 1 000 000

Ukázkový vstup

2
2
2 MS
2 SS
6 SMCFFC
2
1 M
1 C
3 SSF

Ukázkový výstup

0
2

Vysvětlení ukázkového vstupu a výstupu

V prvním vstupu si Pali vybírá mezi dvěma frontami - v první je posloupnost temperamentů MSSS a v druhé MSSMCFFC. Po první minutě odejdou z první fronty první dva sangvinici. Z druhé fronty odejdou dva sangvinici a dva flegmatici. Nové posloupnosti temperamentů tak budou MS a MMCC. První fronta se již dále nebude měnit, zatímco z druhé fronty po chvíli odejdou i zbylí dva melancholici a cholerici. Délka nejkratší fronty je tedy v tomto případě 0. Ve druhém vstupu máme dvě fronty - v první je posloupnost temperamentů MC a ve druhé je to MSSF. Z druhé fronty po první minutě odejde dvojice sangviniků a v obou frontách tak nakonec zbudou dva lidé.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)