让我们引入 $$[x,n] = x + x + \cdots + x = \sum_{i=1}^{n} x$$ 的名称,其中 x 是字符串,n 是正整数,操作“ + ”是字符串连接操作。例如,[abc, 2] = abcabc。
如果我们可以从字符串 t 中删除一些字符并获得字符串 s,我们就会说可以从字符串 t 获得字符串 s。例如,从字符串xacbac中可以得到字符串ab和aсba,而不能从中得到字符串bx和aaa。
Sereja 有两个字符串,w = [a, b] 和 q = [c, d]。他想找到这样的最大整数p(p > 0),使得可以从字符串w中得到[q, p]。
输入
第一行包含两个整数 b, d (1 ≤ b, d ≤ 107)。第二行包含字符串 a。第三行包含字符串 c。给定的字符串不为空且由小写英文字母组成。它们的长度不超过100。
输出
在一行中打印一个整数——最大的数 p。如果所需的 p 值不存在,则打印 0。
示例
输入 #1
10 3 abab bab
输出 #1
3