题目描述

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

安迪的生活很美好，直到有一天，他把自己即将结婚的计划告诉了未来的外婆（即他伴侣的奶奶）。得知安迪打算与她的孙女生 $N$ 个孩子后，外婆给了他 $N$ 个名字，要求他使用这些名字。而且，第 $i$ 个名字只能用于第 $i$ 个孩子。

经过与外婆的长时间争论，安迪达成了协议：第 $i$ 个孩子的名字必须是外婆给的第 $i$ 个名字的子序列。字符串 $A$ 是字符串 $B$ 的子序列，如果 $A$ 可以通过从 $B$ 中删除零个或多个字符（不改变剩余字符的顺序）得到，例如 ABC 是 DAEBCCB 的子序列，但 EFG 不是 FABEGC 的子序列。

尽管安迪不喜欢外婆给的名单，但他仍然希望通过证明自己既能满足外婆的愿望，也能满足自己的愿望（即每个孩子的名字在字典序上都大于他/她所有年长的兄弟姐妹的名字），来给伴侣留下深刻印象。然而，安迪想知道，孩子们名字的总长度最大可能是多少？

例如，设 $N = 3$，外婆给出的名字分别为（KARIM、PARBUDI、CHANDRA）。以下是几个满足安迪愿望的名字集合示例：

• [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$。
• $\dots$

在这个例子中，所有满足安迪愿望的名字集合中，最大总长度为 $16$。注意，在某些情况下可能无法获得有效的名字集合。此时，应输出 -1。例如，设 $N = 2$，外婆给出的名字分别为（ZORO、ANDI）。在这个例子中，第二个名字的所有子序列在字典序上都小于第一个名字的所有子序列，因此无法得到有效的名字集合。

输入格式

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

输出格式

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

3
KARIM
PARBUDI
CHANDRA

16

2
ZORO
ANDI

-1

7
HAVE
FUN
IN
ICPC
JAKARTA
TWENTY
EIGHTEEN

25

提示

样例输入 #3 的解释

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

翻译由 DeepSeek V3.2 完成