Problem C
Hraðskrif

Keyboard eftir DomAlberts, Pixabay

Bjarki setur því upp orðabók á tölvuna sína sem inniheldur öll þau orð sem eru í textanum sem hann vill skrifa. Til dæmis getur textinn sem Bjarki skrifar verið ANNA OG AMMA ETA MAT SAMAN sem krefst þess að Bjarki slær á $26$ lykla. Ef hann notar orðabókina og slær á lyklana AN! O! AM! E! M! S!, þar sem að ! táknar að Bjarki hafi ýtt á TAB takkann, þá slær hann á $19$ lykla og sparar sér því $7$ lykla. Athugið að hann getur ekki notað TAB takkann strax á eftir A því það er óvíst á þeim punkti hvort hann vill skrifa ANNA eða AMMA. Athugið einnig að ef aðeins eitt orð er í orðabókinni þá getur Bjarki slegið á TAB takkann strax, því þó hann hafi ekki slegið inn neinn staf, þá er aðeins eitt orð sem kemur til greina.

Gefin textinn sem Bjarki skrifar, hvað getur hann sparað sér marga áslætti á lyklaborðinu?

Inntak

Fyrsta línan inniheldur eina heiltölu $1\le n\le 5\cdot {10}^5$, fjöldi orða sem Bjarki skrifar í textanum. Næsta lína inniheldur textann sem Bjarki skrifar. Textinn samanstendur af einu eða fleiri orðum sem eru aðskilin með bilum og er fjöldi tákna í mesta lagi ${10}^6$. Orðin innihalda einungis hástafi úr enska stafrófinu.

Úttak

Skrifið út eina línu með fjölda áslátta á lyklaborðið sem Bjarki sparar sér.

Stigagjöf

6
ANNA OG AMMA ETA MAT SAMAN

7

7
BARBARA ARA BAR ARA ARABA BARA RABBABARA

9

1
INSTANT

6