← 返回题目列表

Codeforces · 314/B

B. Sereja 和期间

中文机器翻译题面 查看原题

让我们引入 $$[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