Zadanie

Gól práve strelil…

Počet bodov: 45

Slovakistan žije futbalom! Má dve populárne mužstvá - KSP (Kopeme Silno, Pezinok) a FKS (Futbaloví Králi, Senec).

Nanešťastie po výstavbe nových športových hál, zavlažení trávnikov, a zainvestovaní do cibuliek tulipánov nezostalo klubom práve veľa peňazí na nakúpenie nových dresov.

Rozhodli sa, že dresy teda nakúpia spolu. Problém s tým že jeden dres budú nosiť dvaja futbalisti je však ten, že na drese má byť okrem čísla napísaná (časť) futbalistovho mena. Presnejšie, futbalistov dres musí mať na sebe prefix jeho mena (možno úplný, možno prázdny).

Na dresoch teda musia byť také mená, že si každý hráč KSP vie obliecť dres s vyhovujúcim nápisom, a následne si vie aj každý hráč FKS obliecť dres s vyhovujúcim nápisom.

Samozrejme, mohli na každý dres vytlačiť len číslo a prázdny reťazec, ktorý je vyhovujúci prefix každého mena. Ale na to sa fanúšikom aj komentátorom horšie pozerá, lebo sa im hráči ťažšie rozlišujú.

Pomôžte Slovakistanskému futbalu, a navrhnite takú sadu dresov, aby súčet dĺžok nápisov na nich bol čo najväčší.

Úloha

Oba tímy pozostávaju z \(N\) hráčov. Každý hráč má meno - neprázdny reťazec veľkých písmen anglickej abecedy.

Hráč si môže obliecť dres vtedy, ak je na ňom napísaný prefix jeho mena. Dĺžka nápisu je počet znakov v ňom.

Zistite, aký najväčší súčet dĺžok nápisov môže byť na dresoch tak, aby si celé mužstvo KSP vedelo obliecť dresy, a neskôr celé mužstvo FKS tiež.

Vstup a Výstup

V prvom riadku je číslo \(N\) - počet hráčov v oboch mužstvách.

V druhom riadku je \(N\) neprázdnych reťazcov veľkých písmen anglickej abecedy - mená hráčov KSP. V treťom riadku sú v rovnakom formáte mená hráčov FKS.

Vypíšte jedno číslo - najväčší súčet dĺžok nápisov na dresoch, aby si ich vedeli obliecť obe mužstvá.

V prvej sade \(N \leq 50\) a dĺžky mien sú do \(50\). V druhej sade \(N \leq 200\) a dĺžky mien sú do \(500\). V tretej \(N \leq 10^5\), súčet dĺžok všetkých mien na vstupe nepresiahne \(600\,000\), a žiadne meno nebude mať viac ako \(100\) znakov.

Príklady

Input:

3
KOVAC BOROVICA DOBEHOL
DOHRAL KOVACIC LEMUR

Output:

7

Môžeme vyrobiť dresy s nápismi “KOVAC”, “DO”, "" (prázdny reťazec). Z tímu KSP si KOVAC oblečie dres “KOVAC”, BOROVICA "“, a DOBEHOL ”DO“. FKSáci zas vedia priradiť DOHRALovi ”DO“, KOVACICovi ”KOVAC“, a LEMURovi ”". Dokopy majú nápisy 7 znakov, a lepšie to nejde.

Input:

2
ABRAKA ABKRABA
ABRYBU ABKRAVU

Output:

8

“ABR” a “ABKRA”