3203 - 正确的牛语

奶牛有她们自己的字典,里面的有 W1 \le W \le 300)个词,每个词的长度不超过 25,且由小写字母组成。她们在交流时,由于各种原因,用词总是不那么准确。比如,贝茜听到有人对她说 browndcodw,确切的意思是 browncow,多出了两个 d。这两个 d 大概是身边的噪音。

奶牛们发觉辨认那些奇怪的信息很费劲,所以她们就想让你帮忙辨认一条收到的消息,即一个只包含小写字母且长度为 L1 \le L \le 600)的字符串。有些时候,这个字符串里会有多余的字母,你的任务就是找出最少去掉几个字母就可以使这个字符串变成准确的"牛语"(即奶牛字典中某些词拼接成的一个序列)。

输入

• 第1行:两个用空格隔开的整数,W和L.

• 第2行:一个长度为L的字符串,表示收到的信息.

• 第3行至第W+2行:奶牛的字典,每行一个词.

输出

一个整数,表示最少去掉几个字母就可以使之变成准确的"牛语".

样例

输入

6 10
browndcodw
cow
milk
white
black
brown
farmer

输出

2

来源

USCAO

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题