Problem
Il codice di Evan contiene n variabili. Ogni variabile ha un nome univoco, composto solo da lettere minuscole (minuscole) inglesi. Un giorno Evan decise di accorciare il suo codice.
Vuole sostituire il nome di ogni variabile con il suo prefisso non vuoto in modo tale che i nuovi nomi rimangano distinti a coppie (ma il nuovo nome di qualche variabile può essere lo stesso del vecchio nome di questa o di un'altra variabile). Tra tutte queste possibili sostituzioni, vuole trovarne una per la quale la lunghezza totale dei nomi delle variabili sia minima.
La stringa a è un prefisso della stringa b se puoi rimuovere alcuni (possibilmente nessuno) caratteri dalla fine della stringa b e ottenere a.
Trova la lunghezza totale minima possibile dei nuovi nomi.
Inserimento:
La prima riga contiene un singolo numero intero n (1 ≤ n ≤ 10
5) — numero di variabili nel codice di Evan.
Le successive n righe contengono nomi di variabili, uno per riga. Ogni nome non è una stringa vuota e contiene solo lettere inglesi minuscole (minuscole). La lunghezza totale di tutte queste stringhe non è superiore a 10
5. Tutti i nomi delle variabili sono diversi.
Uscita:
Stampa un singolo numero intero — la lunghezza totale minima possibile dei nuovi nomi di variabile.
Esempi:
| Input |
Uscita |
3
codice |
6 |
5
abba
ab
ab
aa
aacada |
11 |
3
telegramma
digitale
resistenza |
3 |
Spiegazioni:
Nel primo esempio, una delle migliori opzioni sarebbe quella di abbreviare i nomi nell'ordine in cui vengono inseriti in "cod", "co", "c".
Nel secondo esempio, puoi abbreviare il cognome in "aac" e il nome prima di "a" senza modificare altri nomi di variabile.