[ABC343] G - Compress Strings

G - Compress Strings

Time Limit: 5 sec / Memory Limit: 1024 MB

题面

分数: 600 分

给定 个字符串 。

找到包含所有这些字符串作为子字符串的最小长度的字符串。

这里，字符串 包含字符串 作为子字符串，如果 可以通过从 的开头删除零个或多个字符以及从结尾删除零个或多个字符来获得。

限制条件

• 是一个整数。
• 是由小写英文字母组成的长度至少为 的字符串。
• 的总长度最多为 。

输入

输入以以下格式从标准输入给出：

输出

以整数形式输出答案。

输入样例 1

3
snuke
kensho
uk

输出样例 1

9

字符串 snukensho 的长度为 ，包含了所有 、 和 作为子字符串。

具体来说，snukensho 的第一到第五个字符对应于 ，第四到第九个字符对应于 ，第三到第四个字符对应于 。

没有比 更短的字符串包含了所有的 、 和 作为子字符串。因此，答案为 。

输入样例 2

3
abc
abc
arc

输出样例 2

6

输入样例 3

6
cmcmrcc
rmrrrmr
mrccm
mmcr
rmmrmrcc
ccmcrcmcm

输出样例 3

27