Not so rude!

After many adventures, T'Challa faces his final battle against Killmonger. However, since both heroes are exhausted, they decide to resolve their differences through a more peaceful intellectual competition.

The competition rules are as follows: Killmonger first creates a string $s_1{s}_2\dots s_n$, composed of $n$ lowercase Latin letters.

The roughness of a string $t_1{t}_2\dots t_k$ is defined as the number of pairs of integers $(i,j)$, where $1\le i<j\le k$, such that $t_i=$ «a» and $t_j=$ «b». In other words, the roughness is the number of ways to delete all characters except two, leaving the sequence «a» followed by «b».

Once Killmonger has created the string, T'Challa must select a non-empty substring $s_l{s}_{l+1}\dots s_r$. The roughness of this chosen substring must not exceed the number $c$, or T'Challa will face a technical defeat for exceeding the allowed roughness.

T'Challa wins if he selects the longest possible substring from all those whose roughness does not exceed $c$. If there are multiple substrings of maximum length, any of them will suffice. T'Challa doesn't need your help in finding the substring itself, but he asks you to determine the maximum possible length of such a substring.

Input

The first line of input contains two integers $n$ and $c$—the length of the string created by Killmonger, and the maximum allowed roughness of the chosen substring ($1\le n\le 10^6$, $0\le c\le 10^{18}$).

The second line contains the string $s$, created by Killmonger. The string consists of $n$ lowercase Latin letters.

Output

Output a single number—the maximum length of a substring of the given string that has a roughness not exceeding $c$.

Examples

Scoring

This problem includes six subtasks. Each subtask has additional constraints as specified below. To earn points for a subtask, you must pass all tests for that subtask, as well as all tests for all preceding subtasks.

1. ($6$ points): $n\le 3$;

2. ($12$ points): $n\le 50$;

3. ($18$ points): $n\le 700$;

4. ($18$ points): $n\le 5000$;

5. ($24$ points): $n\le 10^5$;

6. ($22$ points): full constraints.