Codeforces 900E. Maximum Questions

Vasya wrote down two strings s of length n and t of length m consisting of small English letters ‘a‘ and ‘b‘. What is more, he knows that string t has a form “abab…“, namely there are letters ‘a‘ on odd positions and letters ‘b‘ on even positions.

Suddenly in the morning, Vasya found that somebody spoiled his string. Some letters of the string s were replaced by character ‘?‘.

Let’s call a sequence of positions i, i + 1, …, i + m – 1 as occurrence of string t in s, if 1 ≤ inm + 1 and t1 = si, t2 = si + 1, …, tm = si + m – 1.

The boy defines the beauty of the string s as maximum number of disjoint occurrences of string t in s. Vasya can replace some letters ‘?‘ with ‘a‘ or ‘b‘ (letters on different positions can be replaced with different letter). Vasya wants to make some replacements in such a way that beauty of string s is maximum possible. From all such options, he wants to choose one with the minimum number of replacements. Find the number of replacements he should make.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the length of s.

The second line contains the string s of length n. It contains small English letters ‘a‘, ‘b‘ and characters ‘?‘ only.

The third line contains a single integer m (1 ≤ m ≤ 105) — the length of t. The string t contains letters ‘a‘ on odd positions and ‘b‘ on even positions.

Output

Print the only integer — the minimum number of replacements Vasya has to perform to make the beauty of string s the maximum possible.

Examples

Note

In the first sample string t has a form ‘a‘. The only optimal option is to replace all characters ‘?‘ by ‘a‘.

In the second sample using two replacements we can make string equal to “aba?aba??“. It is impossible to get more than two occurrences.

题意简述

给出一个长度为 n 字符串 S,包含 ‘a’、’b’、’?’,其中 ‘?’ 可以通过花费 1 的代价变成 ‘a’ 或 ‘b’。另外还有一个长度为 m 的字符串 T,奇数位置上都是 ‘a’,偶数位置上都是 ‘b’。

现在消耗尽可能少的代价使得字符串 S 包含最多的不相交字符串 T。

分析

先处理出每一位能否作为一个 T 串的结尾,只要记 $g(i, 0/1)$ 表示当第 i 位为 ‘a’ 或 ‘b’ 时,从这一位往前最长可以覆盖形如 “abab……” 或 “baba……” 的字符串。只要这个数大于等于 m,并且与 T 的结尾字符一致,那么这一位就可以做 T 串的结尾,代价就是区间内 ‘?’ 的个数,用一个前缀和数组就可以了。

然后考虑 DP,一开始很容易想到记 $f(i,j)$ 表示前 i 位,组成 j 个 T 串的最小代价,仔细分析可以发现,j 这一维也是满足最优子结构的,所以可以把组成的 T 串的个数和花费的代价一起记下来,状态只要 $f(i)$ 一维就好了。

 

发表评论