Maximizing 'abab' Subsequences with Swaps

Given a string s consisting only of the characters 'a' and 'b' of length ( n ), you are allowed to perform exactly ( k ) swaps. In each swap, you may exchange the characters at any two distinct positions in the string. Your task is to maximize the number of non-overlapping occurrences of the substring abab in the resulting string.

A substring is defined as a contiguous part of the string, and the occurrences must not overlap.

Note: When ( k = 0 ), no swap is allowed and you must count the subsequences directly from the original string.

For example, if ( n = 8 ), ( s = \texttt{abbaabab} ) and ( k = 2 ), one possible sequence of operations can yield two non-overlapping occurrences of ( abab ).

inputFormat

The input is given from standard input in the following format:

• The first line contains an integer ( n ), the length of the string.
  
• The second line contains a string ( s ) of length ( n ) consisting only of the characters 'a' and 'b'.
  
• The third line contains an integer ( k ), the number of swaps allowed.

outputFormat

Output a single integer representing the maximum number of non-overlapping occurrences of the substring abab that can be achieved after exactly ( k ) swaps.## sample

8
abbaabab
2

2