Let's introduce the designation <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/67a1d1d8bf722172a43f9417e83a8026881355d4.png" style="max-width: 100.0%;max-height: 100.0%;"/>, 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* &gt; 0), that [*q*, *p*] can be obtained from string *w*.
The first line contains two integers *b*, *d* (1 ≤ *b*, *d* ≤ 10<sup class="upper-index">7</sup>). 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, p = map(int, input().split())
s1 = input()
s2 = input()

cnt = [0] * len(s2)
nxt = [0] * len(s2)

for i in range(len(s2)):     # 从模式串s2的第i位起，扫一遍s1，看有几次完整匹配s2（放在cnt[i]里）， 并且匹配到了s1的哪一位（放在nxt[i]里)
    pos = i
    for j in range(len(s1)):
        if s1[j] == s2[pos]:
            pos += 1
            if pos == len(s2):   # 得到一个完整匹配
                cnt[i] += 1
                pos = 0       # 从s2的头开始重新、循环匹配
    nxt[i] = pos

ans = 0
poss = 0
for i in range(b):    # b是串s1重复出现的次数, 这里的b遍循环，相当于s2从某一位起扫描s1，看有几次匹配，累加这些匹配，并及时更新开始扫描点，就能得到结果
    ans += cnt[poss]
    poss = nxt[poss]

print(ans // p)