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

У мальчика Васи в блокноте были записаны две строки s длины n и t длины m, состоящие из букв «a» и «b» латинского алфавита. Причем Вася знает, что строка t имеет вид «abab...», то есть на нечетных позициях строки стоит буква «a», а на четных — «b».

Вдруг утром Вася обнаружил, что кто-то испортил его строку s. Некоторые буквы s были заменены на символ «?».

Назовем последовательность позиций i, i + 1, ..., i + m - 1 вхождением строки t в s, если 1 ≤ i ≤ n - m + 1 и t1 = si, t2 = si + 1, ..., tm = si + m - 1.

Мальчик оценивает красоту строки s, как максимальное количество непересекающихся вхождений строки t в нее. Вася может заменить некоторые из символов «?» на «a» или «b» (символы на разных позициях можно заменять на разные буквы). Вася хочет произвести замены так, чтобы красота строки s была максимально возможной. Из всех таких вариантов он хочет заменить как можно меньше символов «?». Найдите, сколько замен он должен сделать.

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

Первая строка содержит одно целое число n (1 ≤ n ≤ 105) — длину строки s.

Вторая строка входных данных содержит строку s длины n, состоящую только из букв «a» и «b» латинского алфавита, а также символов «?».

Третья строка содержит целое число m (1 ≤ m ≤ 105) — длину строки t. Сама строка t содержит «a» на нечетных позициях, и «b» на четных.

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

Выведите единственное целое число — минимальное количество замен, которое должен сделать Вася, чтобы сделать красоту строки s максимально возможной.

Примеры
Входные данные
5
bb?a?
1
Выходные данные
2
Входные данные
9
ab??ab???
3
Выходные данные
2
Примечание

В первом примере строка t имеет вид «a». Единственный оптимальный вариант — заменить все символы «?» на «a».

Во втором примере используя две замены можно получить строку «aba?aba??». Больше двух вхождений получить нельзя.