B. Сережа и периоды
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Введем обозначение, , где 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