You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

古籍中有 $2n$ 条咒语，需要将其分为 $n$ 条「引」和 $n$ 条「根」，并任意配对形成 $n \times n$ 对咒语。每对咒语的「最长公共前缀长度」之和需最大化。

• 最长公共前缀：两个字符串从首字符开始连续相同的字符数。

输入

• 第一行：整数 $n$（$1 \leq n \leq 10^5$），表示魔咒的对数。

• 接下来 $2n$ 行：每行一个由小写英文字母组成的字符串 $S$（$1 \leq |S| \leq 10^5$），表示咒语。

• 数据保证：$\sum |S| \leq 2 \times 10^5$。

输出

输出一个整数，表示所有配对方式中，最长公共前缀长度之和的最大值。

样例

输入

1
ennaimez
ennus

输出

3

样例2

输入

3
why
soul
spell
well
weels
whom

输出

7

样例提示

• 样例 1：无论哪条作为「引」或「根」，唯一配对的最长公共前缀为「enn」，长度为 3。
• 样例 2：分组为「引」=$\{why, soul, well\}$，「根」=$\{spell, weels, whom\}$，配对后的最长公共前缀长度之和为 $7$

数据分布

$20\%$ 的样例 $1 \leq n \leq 5$， $1 \leq |S| \leq 10$。

$40\%$ 的样例 $1 \leq n \leq 100$， $1 \leq |S| \leq 100$。

$100\%$ 的样例 $1 \leq n \leq 10^5$， $1 \leq |S| \leq 10^5$，$\sum |S| \leq 2 \times 10^5$。