描述

农夫约翰对他的高产奶牛Bessie进行了DNA测序。DNA序列是由字母'A'、'C'、'G'和'T'组成的有序列表（字符串）。

通常，DNA测序的结果是一组代表DNA片段而非完整DNA链的字符串。例如，像$GATTA$和$TACA$这样的字符串对很可能代表完整的字符串$GATTACA$，因为在测序过程中重叠的字符会被合并。

合并一对字符串需要找到两者之间的最大重叠部分，然后在拼接时消除重复部分。重叠部分必须是一个字符串的末尾与另一个字符串的开头，而不能出现在字符串的中间。

举例说明：

• 字符串$GATTACA$和$TTACA$可以完全重叠。
• 字符串$GATTACA$和$TTA$则完全没有重叠，因为匹配的字符出现在一个字符串的中间而非开头或结尾。以下是合并字符串的示例（包括无重叠的情况）：
  • $GATTA + TACA \rightarrow GATTACA$
  • $TACA + GATTA \rightarrow TACAGATTA$
  • $TACA + ACA \rightarrow TACA$
  • $TAC + TACA \rightarrow TACA$
  • $ATAC + TACA \rightarrow ATACA$
  • $TACA + ACAT \rightarrow TACAT$

给定一组$N$（$2 \leq N \leq 7$）个DNA序列，每个序列的长度在$1$到$7$之间。通过重复合并所有$N$个字符串（使用上述方法），找到并打印可能获得的最短序列的长度。所有字符串必须合并到最终序列中。

输入

第1行：一个整数$N$
第2行到第$N+1$行：每行包含一个DNA子序列

输出

第1行：通过合并子序列可能获得的最短字符串的长度。始终可以（且必须）合并所有输入字符串以获得该字符串。

输入样例1

4  
GATTA  
TAGG  
ATCGA  
CGCAT  

输出样例1

13  

提示

样例解释：
最短字符串为"CGCATCGATTAGG"。

来源

USACO 2006年2月青铜组