403044: GYM100981 B Замена букв

B. Замена буквограничение по времени на тест1 секундаограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Иван очень любит читать газеты, особенно ему интересны политические новости и новости спорта. Также у Ивана есть любимая строка s.

У Ивана очень много свободного времени, да и читает он очень быстро, а вот газет, которые ему интересны, за день выходит не так много. Поэтому в последнее время после прочтения очередной газеты Иван стал считать количество вхождений своей любимой строки s в текст t, написанный в газете, в качестве подстроки. Подстрокой строки x называется последовательность подряд идущих символов строки x.

Но вскоре и с подсчётом вхождений Иван стал справляться очень быстро, и он решил после прочтения очередной газеты заменить в своей любимой строке не более k символов таким образом, чтобы максимизировать количество вхождений изменённой строки s в текст газеты t.

Перед вами стоит задача помочь Ивану и посчитать максимальное количество вхождений его любимой строки s после замены в ней не более k символов в текст газеты t. Ивану не обязательно заменять ровно k букв, и, возможно, ему даже не придётся заменять ни одной буквы. Заменять букву из строки s можно на любую другую.

Входные данные

В первой строке входных данных записаны три целых числа n, m и k (1 ≤ n ≤ m ≤ 250, 0 ≤ k ≤ n) — длина строки s, длина строки t и количество символов, которые может заменить Иван в своей любимой строке, соответственно.

Во второй строке входных данных следует непустая строка s, состоящая из n строчных букв английского алфавита, — любимая строка Ивана.

В третьей строке входных данных следует непустая строка t, состоящая из m строчных букв английского алфавита, — текст, написанный в газете. Гарантируется, что длина строки s не превышает длины строки t.

Выходные данные

Выведите единственное целое число — максимальное количество вхождений любимой строки Ивана s после замены в ней не более k символов в текст газеты t.

ПримерыВходные данные

2 4 1
zz
azaz

Выходные данные

2

Входные данные

3 10 2
aca
accaccacca

Выходные данные

3