← 返回题目列表

Codeforces · 900/E

E. 最大问题数

中文机器翻译题面 查看原题

Vasya 写下了两个长度为 n 的字符串 s 和长度为 m 的 t,由小英文字母“a”和“b”组成。更重要的是,他知道字符串t的形式为“abab...”,即奇数位置有字母'a',偶数位置有字母'b'。

早上,瓦夏突然发现有人弄坏了他的琴弦。字符串 s 的一些字母被字符“?”替换。

如果 1 ≤ i ≤ n - m + 1 并且 t1 = si, t2 = si + 1, ..., tm = si + m - 1,我们将位置序列 i, i + 1, ..., i + m - 1 称为字符串 t 在 s 中的出现。

男孩将字符串 s 的美感定义为字符串 t 在 s 中出现的最大不相交次数。 Vasya 可以替换一些字母 '?'与'a'或'b'(不同位置的字母可以用不同的字母替换)。 Vasya 想要进行一些替换,以使 string s 的美观最大化。他想从所有这些选项中选择一个替换次数最少的。求出他应该进行的替换次数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — s 的长度。

第二行包含长度为 n 的字符串 s。它包含小英文字母“a”、“b”和字符“?”仅有的。

第三行包含一个整数 m (1 ≤ m ≤ 105) — t 的长度。字符串 t 在奇数位置包含字母“a”,在偶数位置包含字母“b”。

输出

打印唯一的整数——Vasya 必须执行的最小替换次数,以使字符串 s 的美观最大化。

示例

输入 #1

5
bb?a?
1

输出 #1

2

输入 #2

9
ab??ab???
3

输出 #2

2

注意

在第一个示例字符串 t 中,其形式为“a”。唯一的最佳选择是替换所有字符“?”按“a”。

在第二个示例中,使用两次替换,我们可以使字符串等于“aba?aba??”。不可能出现两次以上。