A9002 | 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$ .

The first line contains two integers $b$ , $d$ $(1<=b,d<=10^{7})$ . 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$ .

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