Maximum Questions

Vasya는 영문 소문자 'a'와 'b'로 구성된 길이 n의 문자열 s와 길이 m의 문자열 t를 적었다. 또한 그는 문자열 t가 "abab..." 형태라는 것, 즉 홀수 위치에는 문자 'a'가 있고 짝수 위치에는 문자 'b'가 있다는 것을 알고 있다.

어느 날 아침, Vasya는 누군가가 자신의 문자열을 망쳐 놓았다는 것을 발견했다. 문자열 s의 일부 문자가 문자 '?'로 바뀌어 있었다.

위치들의 수열 i, i + 1, ..., i + m - 1에 대해, 1 ≤ i ≤ n - m + 1이고 t1 = si, t2 = si + 1, ..., tm = si + m - 1이면 이를 s에서 문자열 t의 등장이라고 하자.

소년은 문자열 s의 아름다움을 s에서 서로 겹치지 않는 문자열 t의 등장 개수의 최댓값으로 정의한다. Vasya는 일부 문자 '?'를 'a' 또는 'b'로 바꿀 수 있다(서로 다른 위치의 문자는 서로 다른 문자로 바꿀 수 있다). Vasya는 문자열 s의 아름다움이 가능한 한 최대가 되도록 일부 문자를 바꾸고 싶다. 그러한 모든 방법 중에서 바꾸는 횟수가 최소인 방법을 선택하려 한다. 그가 바꿔야 하는 횟수를 구한다.

첫 번째 줄에는 하나의 정수 n (1 ≤ n ≤ 105)가 주어진다. 이는 s의 길이이다.

두 번째 줄에는 길이 n의 문자열 s가 주어진다. 이 문자열에는 영문 소문자 'a', 'b'와 문자 '?'만 포함된다.

세 번째 줄에는 하나의 정수 m (1 ≤ m ≤ 105)가 주어진다. 이는 t의 길이이다. 문자열 t의 홀수 위치에는 문자 'a'가 있고 짝수 위치에는 문자 'b'가 있다.

문자열 s의 아름다움을 가능한 한 최대화하기 위해 Vasya가 수행해야 하는 최소 변경 횟수인 유일한 정수를 출력한다.

첫 번째 예제에서 문자열 t는 'a' 형태이다. 유일한 최적의 방법은 모든 문자 '?'를 'a'로 바꾸는 것이다.

두 번째 예제에서는 두 번의 변경을 사용하여 문자열을 "aba?aba??"와 같게 만들 수 있다. 두 개보다 많은 등장을 얻는 것은 불가능하다.