UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4460. [Jsoi2013]广告计划

Statistics 下载数据

Description

如今,在建筑的墙面上或者篱笆桩的表面上涂上一些广告,是一种新的吸引眼球的方法。
现在,小G 运营的一家小公司,决定也试着这样做做广告。小G在他的篱笆桩上腾出了一
些地方供广告使用。每一个篱笆桩都是一个水平的1*1*L的 4 棱柱,其中有一个 1*L的面
是可以做广告的。1*L的面上划出了 L个1*1 的小正方形(更具体地说是连续L个水平排列
的正方形),每个正方形内写上一个字母。 时间久了,广告做多了难免会出现一些比较麻
烦的情况,比如计划改变或者制作出错,因此小 G 的仓库里面积累了好多没有用的,上面
已经写上 L 个字母的篱笆桩。(所有的篱笆桩的大小都是一样的,他们唯一的区别仅仅在
于上面写了什么字母)。 小G 决定对于这些篱笆桩进行重新利用,并且有了一些新的想法。
如果将这些篱笆桩竖直的叠放起来,并且依次从左往右,对于每一个篱笆桩顺次从上到下读
出上面的字母,那么我们可以得到一些新的比较长的单词,如下图:


这些新的单词能满足小G的一些新的需要。当然,基于美学考虑,小G 是不允许你删改篱笆
桩上已经写上的字母的。 我们更具体地描述这个过程。我们将 K个长度为 L的篱笆桩叠在
一起,可以得到一个写有 K行L列共K*L个字母的面,每一个字母都在对应的唯一的格子里。
我们从左上角开始依次向下读出每一个字母可以得到一个字母的序列,比如上图中的这个例子,
那么我们读出的结果就是“TOEIIZENITKN”。如果,这个串中有我们所需要的单词,那么显然
我们只需要将一些格子刷白,就可以得到我们所需要的了。举个例子,比如小G想要给圣彼得堡
的足球队泽尼特队做个广告,那么很显然只要按照上图中的做法就可以达到小G想要的效果了。
现在小G已经想好了要做怎样的广告,同时也提供给你了小G仓库中的篱笆桩的类型的描述,
你可以认为每一种类型的篱笆桩都是有无数个的。现在小G 想知道至少需要多少个篱笆桩叠起来
才可以做出小G想要的广告。

Input

第一行两个自然数,N和L。 N≤100,L≤100
接下来N 行,每行包含 L个小写字母,描述一种篱笆桩上写着的字母。保证不同类型的篱笆
桩上的字母序列都是不一样的,每一种类型的篱笆桩都是有无数个。
最后一行是一个长度不超过 200的字符串s,表示小G 想好的广告词。

Output

第一行一个整数K,表示所需要的最少数量的篱笆桩(注意是数量,并不是种类数)。

Sample Input

3 4
tiet
oink
ezin
zenit

Sample Output

3

Hint

Source

By 佚名上传