B. Sereja and Periodstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet'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.InputThe 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.OutputIn a single line print an integer — the largest number p. If the required value of p doesn't exist, print 0.ExamplesInput10 3ababbabOutput3
Input10 3ababbab
Output3
['binary search', 'dfs and similar', 'strings', '*2000']