P7861 [COCI 2015/2016 #2] SAVEZ

有一个秘密行星 S4 居住着一种奇特的动物，它们的学名是 Loda。Savez 协会派出了一个由 Henrik 将军领导的小组来研究 Loda。Henrik 发现，Loda 有心灵传输的能力，他想在他的军队里雇佣他们。 一只 Loda 由 $N$ 个字符串组成，其中第 $i$ 个字符串记为 $x_i$。研究表明，Loda 能进行的心灵传输次数取决于组成它的字符串的一个特殊子序列（不一定是连续的）。字符串 $x_i$ 和 $x_j\ (i

第一行一个整数 $N$，表示组成某一只 Loda 的字符串总数。 接下来 $N$ 行，每行一个仅由大写英文字母构成的字符串 $x_i$，表示构成这一只 Loda 的字符串。

一行一个整数，表示这只 Loda 可以进行心灵传输的次数。

**【样例 1 解释】** 一个最长的子序列为 `A AA AAA`。 **【样例 3 解释】** 子序列中的字符串允许相等，因此一个最长的子序列为 `A A A` 或 `B B B`。 **【数据范围】** 对于 $100\%$ 的数据，$1\le N \le 2\times 10^6，1\le |x_i| \le 2\times 10^6$，**保证 $\sum |x_i|\le 2\times 10^6$**。 **【说明】** **本题数据点得分依原题，满分 120**。 题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #2](https://hsin.hr/coci/archive/2015_2016/contest2_tasks.pdf) **T4 SAVEZ**。