字符串压缩

题目描述

给定 $N$ 个字符串 $S_1, S_2, \ldots, S_N$。

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

这里，如果可以通过从字符串 $S$ 的开头删除零个或多个字符，并从结尾删除零个或多个字符得到字符串 $T$，则称字符串 $S$ 包含字符串 $T$ 作为子串。

输入格式

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

N
S_1
S_2
⋮
S_N

输出格式

以整数形式输出答案。

样例

3
snuke
kensho
uk

9

长度为 $9$ 的字符串 snukensho 包含 $S_1$、$S_2$、$S_3$ 全部作为子串。

具体来说，snukensho 的第 1 到第 5 个字符对应 $S_1$，第 4 到第 9 个对应 $S_2$，第 3 到第 4 个对应 $S_3$。

不存在更短的包含 $S_1$、$S_2$、$S_3$ 全部作为子串的字符串。 因此，答案为 $9$。

3
abc
abc
arc

6

6
cmcmrcc
rmrrrmr
mrccm
mmcr
rmmrmrcc
ccmcrcmcm

27

数据范围

• $N$ 是整数。
• $1 \le N \le 20$
• $S_i$ 是由小写英文字母组成、长度至少为 $1$ 的字符串。
• $S_1, S_2, \dots, S_N$ 的总长度至多为 $2 \times 10^5$