Введем обозначение, 
, где x — строка, n — целое положительное число, а операция « + » обозначает конкатенацию строк. Например, [abc, 2] = abcabc.
Будем говорить, что строку s можно получить из строки t, если можно удалить некоторые символы строки t и получить строку s. Например, строки ab и aсba можно получить из строки xacbac, а строки bx и aaa — нет.
У Сережи есть две строки w = [a, b] и q = [c, d]. Он хочет найти такое максимальное целое число p (p > 0), что [q, p] можно получить из строки w.
В первой строке заданы два целых числа b, d (1 ≤ b, d ≤ 107). Во второй строке содержится строка a. В третьей строке содержится строка c. Заданные строки не пусты и состоят из маленьких латинских букв. Их длины не превосходят 100.
В единственную строку выведите целое число — наибольшее число p. Если не существует искомого значения p, выведите 0.
10 3
abab
bab
3
| Codeforces Round 187 (Div. 1) |
|---|
| Закончено |
