F. No explanation
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个由只包含小写字母的字符串构成的集合 $$$\{s_i\}$$$，你需要在集合中选出一些字符串，并选择一个合适的顺序拼接成一个新字符串。设这个新的字符串为 $$$S$$$，出题人不希望 $$$S$$$ 中存在子序列 luolikong ，即 $$$S$$$ 中不存在一个位置集合 $$$\{\mathrm{pos}_i\}$$$ 满足

1. 集合的大小为 $$$9$$$ 并且 $$$1\le \mathrm{pos}_i\le |S|$$$。

2. 对于所有 $$$1\le i\le 8,\ \mathrm{pos}_i \lt \mathrm{pos}_{i + 1}$$$。

3. 对于长度为 $$$9$$$ 并且满足 $$$t_i = S_{\mathrm{pos}_i}$$$ 的字符串 $$$t$$$，$$$t= $$$ luolikong。

出题人并不想解释这么做的理由。

你只需要计算可能的 $$$S$$$ 的最大长度即可。

Input

第一行包含一个整数 $$$n$$$（$$$1 \le n \le 5000$$$），表示集合 $$$\{s_i\}$$$ 的大小。

接下来的 $$$n$$$ 行，每行包含一个字符串 $$$s_i$$$（$$$1 \le |s_i| \le 5 \times 10^5$$$，$$$\sum|s_i|\le 5\times 10^5$$$）。

Output

输出一行一个整数，表示可能的 $$$S$$$ 的最大长度。

Example
Input
5
zhongzhikong
luo
likelisi
kluikong
likuong
Output
31
Note

一种合法的拼接方案：zhongzhikong kluikong luo likelisi。

容易证明，不存在另一种拼接方案，使得字符串长度大于 $$$31$$$ 且不含子序列 luolikong。