[Usaco2010 Dec]Letter 恐吓信

题目描述

FJ刚刚和邻居发生了一场可怕的争吵，他咽不下这口气，决定佚名发给他的邻居 一封脏话连篇的信。他有无限张完全相同的已经打印好的信件，都包含 N个字母(1 <= n="" <="50,000)。他想剪出其中一些并且粘帖成一个很长的字母串。" fj太懒了，他想用最少的次数裁剪信件。他有一把举世无双的剪刀，他可以从="" 一封信中只剪一刀剪出连续一段。同样，剪一刀可以得到整个完整的字符串。="" 他想知道他最少需要剪多少刀从而获得这封m个字母的长信？="" 保证这总是可能的。="" 考虑下面38个字母的信：="" thequickbrownfoxdo="" gjumpsoverthelazydog="" 以及fj想要获得的9个字母的信：="" foxdog="" dog="" 以上是为了读入方便，实际上这两封信就是：="" thequickbrownfoxdogjumpsoverthelazydog="" foxdogdog="" 由于foxdog已经存在了，fj可以剪一刀得到foxdog。还剩下一个dog，fj可以选择="" 其中任何一个dog剪下来。="" 因此，他一共要剪2刀。="" p="">

---

输入格式

* 第一行： 两个空格分隔的整数： N, M * 第2..?行： 一些行包含N个字母，FJ原来拥有的信，每行不会超过80个字母。 * 第?...?行： 一些行包含M个字母，FJ想要写的信，每行不会超过80个字母。

---

输出格式

* 第1行： FJ获得他想要写的信所需要切的最少次数。

---

样例输入

38 9
THEQUICKBROWNFOXDO
GJUMPSOVERTHELAZYDOG
FOXDOG
DOG

---

样例输出

2

---

提示

没有写明提示

---

题目来源

Gold