题目描述

我们都玩过接龙的游戏，比如："五一劳动节" → "节日快乐" → "乐在其中" → "中游击水" ……

对于一个由若干个字符组成的字符串序列，如果它们满足如下条件，则我们称这个字符串序列是一个 ”字符串接龙环”：

• 任意一对相邻的字符串均满足：前一个字符串的最后一个字符等于后一个字符串的前一个字符；
• 最后一个字符串的最后一个字符等于第一个字符串的第一个字符。

比如：如果选择的字符串按顺序依次为 "onecode", "end", "deep", "pear", "radio"，则因为：

• "onecode" 的最后一个字符等于 "end" 的第一个字符（均为 'e'）
• "end" 的最后一个字符等于 "deep" 的第一个字符（均为 'd'）
• "deep" 的最后一个字符等于 "pear" 的第一个字符（均为 'p'）
• "pear" 的最后一个字符等于 "radio" 的第一个字符（均为 'r'）
• "radio" 的最后一个字符等于 "onecode" 的第一个字符（均为 'r'）

所以这些字符串构成的序列是一个 ”字符串接龙环”。

特别地，如果一个字符串，它本身的第一个字符就等于最后一个字符，比如："tnt"，则这一个字符串构成的序列也是一个 ”字符串接龙环”。

现在给你一个由 $n$ 个字符串组成的字符串序列 $s_1, s_2, \ldots, s_n$。

你需要从中选出若干个字符串，但是不能调整字符串之间的先后顺序（也就是说要选择该字符串序列的一个子序列）。比如：依次选择 $s_3, s_1, s_6$ 是不被允许的，因为 $s_3$ 不应该排在 $s_1$ 前面。

同时，你选择的这些字符串必须构成一个 ”字符串接龙环”。

并且你希望这个 ”字符串接龙环” 中的所有字符串的长度之和尽可能地大。

输入格式

第一行，一个整数 $n(1 \le n \le 2 \cdot 10^5)$，表示字符串个数。

接下来 $n$ 行，每行包含一个字符串，依次表示 $s_1, s_2, \ldots, s_n$。每个字符串仅由小写英文字母组成且长度均不超过 $10$。

输出格式

输出一个整数，表示能够得到的 ”字符串接龙环” 子序列包含的字符串长度之和的最大值。

3
abc
ca
cba

6

4
aab
aab
abc
cbd

0

3
ab
c
def

1

说明/提示

样例解释

• 样例1：最优解是选择 "abc" → "cba"，对应的字符串长度和为 $3 + 3 = 6$；
• 样例2：不存在任何一个子序列是 ”字符串接龙环”；
• 样例3：最优解是选择 "c"，对应的长度和为 $1$。

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 20$
• 对于 $60\%$ 的数据，$n \le 2000$
• 对于 $100\%$ 的数据，$1 \le n \le 2 \cdot 10^5$，且每个字符串的长度均不超过 $10$