I. Музыкальные классики
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Таня придумала игру и теперь целыми днями играет в неё. Игра называется «Музыкальные классики». До начала игры она на асфальте рисует n одинаковых квадратов, выстроенных в ряд слева направо. Квадраты пронумерованы от 1 до n слева направо. В каждом квадрате она рисует одну из семи нот, которые обозначает латинскими буквами от 'A' до 'G', причём i-й квадрат содержит ноту ti.

После этого она выбирает некоторую мелодию s, которая состоит из m нот, воспроизводимых последовательно. Ноты в мелодии пронумерованы от 1 до m в порядке воспроизведения.

До начала воспроизведения Таня встает в некоторый квадрат, в котором записана первая нота мелодии (иными словами, буква s1). Если таких квадратов несколько, то она сама выбирает, в какой из них ей встать.

После этого Таня включает мелодию и в момент, когда начинает звучать вторая нота, она должна перепрыгнуть в квадрат с этой нотой (то есть с буквой s2). Когда начинает звучать третья нота, Таня должна перепрыгнуть в квадрат с третьей нотой (то есть буквой s3). Так она продолжает игру до её окончания. Допустимо, что во время звучания очередной ноты Таня подпрыгнет на месте и приземлится в том же квадрате. Это может произойти, если очередная нота совпадает с предыдущей.

Таня не умеет прыгать дальше, чем на d квадратов влево или вправо. Например, если d = 1, то Таня может прыгать не дальше соседних по стороне квадратов, а если d = 0, то Таня может прыгать только на тот квадрат, в который встанет изначально. Левее квадрата номер один и правее квадрата номер n Таня прыгать не будет, так как это не по правилам!

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

Найдите наибольшую возможную продолжительность игры Тани при её наилучшей стратегии. Если первая нота из мелодии не написана ни в одном из квадратов, то продолжительность игры равна нулю.

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

В первой строке следуют три целых числа n, m и d (1 ≤ n, m ≤ 100, 0 ≤ d ≤ n - 1) — количество квадратов с нотами, количество нот в мелодии и максимальная дальность прыжка Тани.

Во второй строке следует строка t длины n, где ti равно ноте, записанной в i-м квадрате. Гарантируется, что строка t содержит только прописные латинские буквы от 'A' до 'G'.

В третьей строке следует строка s длины m, где sj равно j-й ноте в мелодии. Гарантируется, что строка s содержит только прописные латинские буквы от 'A' до 'G'.

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

Выведите максимальное количество нот, на протяжении воспроизведения которых Таня сможет играть по правилам и игра не закончится.

Примеры
Входные данные
8 3 2
AGFEDCBA
ACF
Выходные данные
2
Входные данные
2 4 1
AB
ABAA
Выходные данные
4
Входные данные
6 3 4
EAGCBF
DAC
Выходные данные
0
Примечание

В первом примере Таня должна изначально встать в квадрат номер 8, в котором написана нота 'A'. После воспроизведения первой ноты она должна прыгнуть в квадрат номер 6, в котором записана вторая нота мелодии 'C'. После этого игра прекратится, так как Таня не сможет допрыгнуть до единственного квадрата с нотой 'F'.

Во втором примере Таня сможет играть на протяжении воспроизведения всех четырёх нот мелодии. Для этого ей нужно изначально встать в квадрат номер 1, затем прыгнуть в квадрат номер 2, после этого прыгнуть в квадрат номер 1 и перед воспроизведением четвёртой ноты подпрыгнуть на месте, то есть остаться в квадрате номер 1.

В третьем примере первая нота мелодии, равная 'D', не записана ни в одном из квадратов, поэтому ответ равен нулю.