Problem
Max는 길이가 n인 두 개의 문자열 s와 길이가 m인 t를 노트에 썼으며 문자 "a"로 구성되었습니다. 그리고 "b" 라틴 알파벳. 또한 Max는 문자열 t가 "abab..." 형식을 갖는다는 것을 알고 있습니다. 즉, 문자 "a"는 문자열의 홀수 위치에 있고 문자 — "비".
갑자기 아침에 Max는 누군가가 그녀의 문자열을 엉망으로 만들었다는 것을 발견했습니다. 일부 s가 "?"로 변경되었습니다.
위치 i, i + 1, ..., i + m - 1의 시퀀스를 1 ≤&thinsp인 경우 s에서 문자열 t의 발생이라고 합시다. ;i ≤ n - m + 1 및 t
1 = s
i, t
2 &thinsp ;= s
i + 1, ..., t
m = s
i + m - 1.
문자열 s의 아름다움은 문자열 t가 겹치지 않는 최대 횟수로 측정됩니다. Max는 일부 "?"를 대체할 수 있습니다. "에" 또는 "b" (위치가 다른 문자는 다른 문자로 대체될 수 있습니다.) Max는 문자열 s의 아름다움이 가능한 한 커지도록 대체를 원합니다. 이러한 모든 옵션 중에서 "?" 문자를 가능한 적게 바꾸려고 합니다. 그녀가 얼마나 많은 교체를 해야 하는지 알아보십시오.
입력:
첫 번째 줄에는 단일 정수 n(1 ≤ n ≤ 10
5) — 문자열 길이 s.
입력의 두 번째 줄에는 문자 "a"로만 구성된 길이 n의 문자열 s가 포함됩니다. 그리고 "b" 라틴 알파벳과 기호 «?».
세 번째 줄에는 정수 m(1 ≤ m ≤ 10
5) — 문자열 길이 t. 문자열 t 자체에는 "a"가 포함됩니다. 홀수 위치에 "b" 짝수에.
출력:
단일 정수 인쇄 — 문자열의 아름다움을 최대한으로 만들기 위해 Vasya가 수행해야 하는 최소 대체 수입니다.
예:
<몸>
| 입력 |
출력 |
5
bb?a?
1 |
2 |
9
ab??ab???
3 |
2 |
설명:
첫 번째 예에서 문자열 t는 "a" 형식입니다. 유일한 최적의 옵션 – 모든 문자 "?" 바꾸기 «a»로.
두 번째 예에서는 두 개의 교체를 사용하여 문자열 "aba?aba??"를 얻을 수 있습니다. 두 개 이상의 항목을 가져올 수 없습니다.