#P5254. [JSOI2013] 广告计划

[JSOI2013] 广告计划

题目背景

如今,在建筑的墙面上或者篱笆桩的表面上涂上一些广告,是一种新的吸引眼球的方法。

题目描述

现在,小G 运营的一家小公司,决定也试着这样做做广告。小G在他的篱笆桩上腾出了一些地方供广告使用。每一个篱笆桩都是一个水平的1*1*L的 4 棱柱,其中有一个 1*L的面是可以做广告的。1*L的面上划出了 L 个1*1 的小正方形(更具体地说是连续L个水平排列的正方形),每个正方形内写上一个字母。 时间久了,广告做多了难免会出现一些比较麻烦的情况,比如计划改变或者制作出错,因此小 G 的仓库里面积累了好多没有用的,上面已经写上 L 个字母的篱笆桩。(所有的篱笆桩的大小都是一样的,他们唯一的区别仅仅在于上面写了什么字母)。 小G 决定对于这些篱笆桩进行重新利用,并且有了一些新的想法。

如果将这些篱笆桩竖直的叠放起来,并且依次从左往右,对于每一个篱笆桩顺次从上到下读出上面的字母,那么我们可以得到一些新的比较长的单词,如下图:

qwq

这些新的单词能满足小G的一些新的需要。当然,基于美学考虑,小G 是不允许你删改篱笆桩上已经写上的字母的。 我们更具体地描述这个过程。我们将 K个长度为 L的篱笆桩叠在一起,可以得到一个写有 K行L列共K*L个字母的面,每一个字母都在对应的唯一的格子里。

我们从左上角开始依次向下读出每一个字母可以得到一个字母的序列,比如上图中的这个例子,那么我们读出的结果就是“TOEIIZENITKN”。如果,这个串中有我们所需要的单词,那么显然我们只需要将一些格子刷白,就可以得到我们所需要的了。举个例子,比如小G想要给圣彼得堡的足球队泽尼特队做个广告,那么很显然只要按照上图中的做法就可以达到小G想要的效果了。

现在小G已经想好了要做怎样的广告,同时也提供给你了小G仓库中的篱笆桩的类型的描述,你可以认为每一种类型的篱笆桩都是有无数个的。现在小G 想知道至少需要多少个篱笆桩叠起来才可以做出小G想要的广告。

输入格式

第一行两个自然数,N和L。

接下来N 行,每行包含 L个小写字母,描述一种篱笆桩上写着的字母。保证不同类型的篱笆桩上的字母序列都是不一样的,每一种类型的篱笆桩都是有无数个。

最后一行是一个字符串s,表示小G 想好的广告词。

输出格式

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

3 4
tiet
oink
ezin
zenit
3

提示

1  N, L  1001~\leq~N,~L~\leq~100

1  s  2001~\leq~|s|~\leq~200