Boekenkasten
Beschrijving
Berend is bibliothecaris. Hij beheert de boeken van de
universiteitsbibliotheek in Preh Fiks. Vanwege de gestage groei van de
collectie is het huidige gebouw te klein geworden, dus de bibliotheek
gaat verhuizen.
Het Probleem
Van deze gelegenheid wil Berend gebruik maken om de boeken op een
andere manier te verdelen over de nieuwe kasten. Hij wil op elke plank
boeken hebben staan, waarvan de naam dezelfde prefix heeft. Maar
de grootste prefix van alle boeken op een plank mag niet voorkomen als
begin van zo'n prefix op iedere andere plank, zodat boeken gemakkelijk
op prefix te vinden zijn.
Voorbeeld: als `Verwachting' en `Verwarring' op één plank
staan (prefix verwa), mogen `Vermoedens' en
`Verlakkerij' niet samen op één andere plank staan (prefix
ver, begin van verwa), maar `Vroomheid' en
`Vrede' wel (prefix vr).
Nou is er altijd te weinig geld, dus hoe minder kasten Berend nodig
heeft, hoe beter.
De Invoer
De eerste regel bevat een getal dat de hoeveelheid runs aangeeft. Dan volgt per
run:
- Een regel met de hoeveelheid planken k in één kast
(1 <= k <= 10).
- Een regel met het aantal boeken p dat (maximaal) op één plank
past (1 <= p <= 30). Neem aan dat alle boeken evenveel ruimte
innemen.
- Een regel met een getal dat het aantal boeken aangeeft.
- Voor ieder boek een regel met daarop de titel. Een titel bestaat
uit de tekens `a'-`z', aangevuld met spaties
tot een lengte van 20 tekens. Alle titels binnen een run zijn verschillend.
De Uitvoer
Per run één getal: de minimale hoeveelheid kasten die Berend nodig heeft.
Voorbeeld
Bij de invoer
2
1
2
2
past
precies
1
2
5
past
pijnlijk
genoeg
niet
precies
hoort de uitvoer
1
5