#1059. 张宇的1000题

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Non_User8

题目描述

张宇老师的1000题真的太难了!

事实是,所有的题目都源自于最简单的知识点。张宇老师通过融合贯通使其复杂化,就有了这样一本1000题了。

也就是说,最新版的张宇1000题本质是是由之前的部分题目修改得到的。

现在,张宇老师开始撰写自己最新版的1000题了。

在张宇老师的题库里有许多题目。张宇老师发现这1000道题里面有许多相似的题目。

也就是说如果题目a和题目b比较类似,那么会导致用他题目a构造新的题目和题目b构造题目会有类似的效果。

张宇老师的题库里,一共有n道题目。每道题目都是一个只包含 小写字母 的字符串。

张宇老师首先创造一道空的题目,然后会进行任意次下述操作得到一个新的字符串拼接到空字符串的后面。

(下述操作会创造一个字符串,但是不会修改原本的字符串)

张宇老师选择一道题库里面的题目然后进行修改,然后可以进行任意次数的以下两种操作。

1.删除某一道题目的开头/结尾字母

2.添加任意一个小写字母到开头/结尾

每进行一次操作需要花费 张宇老师 一分钟的时间。

例如,张宇老师想从 haopp -> marble ,可以先删除开头的一个字母,再删除尾部的3个字母,再添加字母 m 在开头,再添加字母 rble 在结尾。整个过程 张宇老师花费 9 min。

张宇老师想知道,创造一个题目 ,最少需要多少时间。

输入格式

输入的第一行是一个整数(),代表张宇老师题库里的题目数量

接下来行,每行输入一个字符串,代表张宇老师题库内的题目。

保证输入的n个字符串长度

接下来行,输入一个字符串 ,

输出格式

输出一个整数,表示张宇老师花费的最少时间

样例

输入样例

1
haopp
haoppp

输出样例

1

输出样例

5
cqupt
cquut
cqppt
cqqqt
qqqqt
cquptcquutcqcqcq

输出样例

6