Andi 要结婚了！他和他的伴侣计划生 $N$ 个孩子。为了避免将来出现麻烦，Andi 想提前决定所有孩子的名字。具体来说，他希望每个孩子的名字在字典序上都大于他/她的任何一位兄姐。当然，他的伴侣也同意这个想法。如果字符串 $B$ 是字符串 $A$ 的前缀，或者存在一个索引 $i$ 使得 $A_i > B_i$ 且对于所有 $j < i$ 都有 $A_j = B_j$，则称字符串 $A$ 在字典序上大于字符串 $B$。注意，专有名词可以短至一个字符，但不能为空字符串。

生活对 Andi 来说很美好，直到有一天他把这个结婚计划告诉了他未来的外祖母（即他伴侣的祖母）。在得知 Andi 计划与她的孙女共育 $N$ 个孩子后，她给了他 $N$ 个名字供使用。此外，第 $i$ 个名字只能用于第 $i$ 个孩子。

在与外祖母进行了一番长谈后，Andi 达成了一个协议：第 $i$ 个孩子的名字必须是外祖母给出的第 $i$ 个名字的子序列。如果字符串 $A$ 可以通过从 $B$ 中删除零个或多个字符且不改变剩余字符的顺序而得到，则称 $A$ 是 $B$ 的子序列。例如，ABC 是 DAEBCCB 的子序列，但 EFG 不是 FABEGC 的子序列。

尽管 Andi 不喜欢给出的名字列表，但他仍然想通过证明他既能满足外祖母的愿望，又能满足自己的愿望（即每个孩子的名字在字典序上都大于他/她的任何一位兄姐）来打动他的伴侣。然而，Andi 想知道，他们孩子名字的总长度最大可能是多少？

例如，设 $N = 3$，伴侣的祖母给出的名字是 (KARIM, PARBUDI, CHANDRA)。以下是满足 Andi 愿望的几组名字示例：

• [AR, BI, CRA]，总长度为 $2 + 2 + 3 = 7$。
• [ARI, BUDI, CHANDRA]，总长度为 $3 + 4 + 7 = 14$。
• [ARIM, ARUDI, CHANDRA]，总长度为 $4 + 5 + 7 = 16$。
• [AIM, ARBUDI, CHANDRA]，总长度为 $3 + 6 + 7 = 16$。
• ...

在满足 Andi 愿望的所有名字组合中，最大总长度为 $16$。注意，在某些情况下可能无法获得有效的名字组合。在这种情况下，你应该输出 -1。例如，设 $N = 2$，伴侣的祖母给出的名字是 (ZORO, ANDI)。在这个例子中，第 $2$ 个名字的所有子序列在字典序上都小于第 $1$ 个名字的所有子序列，因此，无法获得有效的名字组合。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 15$)，表示孩子的数量。接下来的 $N$ 行，每行包含一个字符串 $S_i$ ($1 \le |S_i| \le 15$)，表示 Andi 未来的外祖母给出的第 $i$ 个名字。$S_i$ 仅包含大写字母 ($S_{ij} \in \{A - Z\}$)。

输出格式

输出一行，包含一个整数，表示孩子名字的最大可能总长度，如果无法获得有效的名字组合，则输出 -1。

样例

样例输入 1

3
KARIM
PARBUDI
CHANDRA

样例输出 1

16

样例输入 2

2
ZORO
ANDI

样例输出 2

-1

样例输入 3

7
HAVE
FUN
IN
ICPC
JAKARTA
TWENTY
EIGHTEEN

样例输出 3

25

说明 3

一种可能的解是 [AVE, FUN, IN, IPC, JAKARTA, NTY, TEEN]，总长度为 $3+3+2+3+7+3+4 = 25$。