CF314B.Sereja and Periods

Let's introduce the designation , where x is a string, n is a positive integer and operation " + " is the string concatenation operation. For example, [abc, 2] = abcabc.

We'll say that string s can be obtained from string t, if we can remove some characters from string t and obtain string s. For example, strings ab and aсba can be obtained from string xacbac, and strings bx and aaa cannot be obtained from it.

Sereja has two strings, w = [a, b] and q = [c, d]. He wants to find such maximum integer p (p > 0), that [q, p] can be obtained from string w.

我们定义符号 ，其中 $x$ 是一个字符串，$n$ 是一个正整数，而运算 “ + ” 表示字符串连接操作。例如，$[abc,\,2] = abcabc$。

我们称字符串 $s$ 可由字符串 $t$ 得到，当且仅当我们能从字符串 $t$ 中删除若干字符（可以是零个或多个），从而得到字符串 $s$。例如，字符串 $ab$ 和 $acba$ 均可由字符串 $xacbac$ 得到，而字符串 $bx$ 和 $aaa$ 则无法由它得到。

Sereja 有两个字符串：$w = [a,\,b]$ 和 $q = [c,\,d]$。他希望找出满足条件的最大正整数 $p$，使得 $[q,\,p]$ 可由字符串 $w$ 得到。

The first line contains two integers b, d (1 ≤ b, d ≤ 107). The second line contains string a. The third line contains string c. The given strings are not empty and consist of lowercase English letters. Their lengths do not exceed 100.

第一行包含两个整数 $b$、$d$（$1 \le b,\,d \le 10^7$）。
第二行包含字符串 $a$。
第三行包含字符串 $c$。
给定的字符串非空，且仅由小写英文字母组成。它们的长度均不超过 $100$。

In a single line print an integer — the largest number p. If the required value of p doesn't exist, print 0.

在一行中输出一个整数——最大的数 $p$。如果所需的 $p$ 值不存在，则输出 0。