CF900E 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

The first line contains a single integer $ n $ ( $ 1

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

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.