El Granjero Juan ha encontrado la secuencia DNA de su vaca productora de leche campeona, las secuencias DNA de Bessie son listas ordenadas (cadenas) conteniendo las letras ~'A', 'C'~, ~'G'~, y ~'T'~.

Como es usual para secuencias DNA, los resultados son un conjunto de cadenas que son fragmentos secuenciados de DNA, no cadenas enteras DNA. Un par de cadenas como '~GATTA~' y '~TACA~' lo más posible es que representen la cadena 'GATTACA' en tanto que los caracteres que se superponen son mezclados, desde que ellos fueron posiblemente duplicados en el proceso de secuenciación.

Mezclar un par de cadenas requiere encontrar la mayor superposiciòn entre las dos y luego eliminarla en tanto las dos cadenas se concatenan. Las superposiciones son entre el final de una cadena y el comienzo de otra cadena, nunca en el medio de una cadena.

Por ejemplo, las cadenas '~GATTACA~' y '~TTACA~' se suporponen completamente. Por otra parte las cadenas '~GATTACA~' y '~TTA~' no tienen ninguna superposición, desde que los caracteres coincidentes aparecen en la mitad de la otra cadena, no al comienzo de la otra. Aquí hay algunos ejemplos de mezclar cadenas, incluyendo aquellas sin superposición:

GATTA + TACA -> GATTACA
TACA + GATTA -> TACAGATTA
TACA + ACA -> TACA
TAC + TACA -> TACA
ATAC + TACA -> ATACA
TACA + ACAT -> TACAT

Dado un conjunto de ~N~ ~(2 \leq N \leq 7)~ secuencias DNA todas las cuales tienen longitudes menor que 50, encuentre e imprima la secuecia más corta posible obtenible mezclando repetidamente todas las ~N~ cadenas usando el procedimiento antes descrito. Todas las cadenas deben ser mezcladas en la secuencia resultante para la secuencia resultante.

Entrada

• Línea 1: Un solo entero ~N~
• Líneas 2..N+1: Cada línea contiene una sola subsecuencia DNA

Salida

La longitud de la cadena más corta posible obtenida mezclando las subsecuencias. Es siempre posible – y requerido – mezclar todas las cadenas de la entrada para obtener esta cadena.

Ejemplo de Entrada

4
GATTA
TAGG
ATCGA
CGCAT

Ejemplo de Salida

13

Detalles de la Salida: Tal cadena es "~CGCATCGATTAGG~".