Not so rude!#10300
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 lowercase Latin letters.
The roughness of a string t_1 t_2 \dots t_k is defined as the number of pairs of integers , 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 , 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 . 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.
The first line of input contains two integers and —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 , created by Killmonger. The string consists of lowercase Latin letters.
Output a single number—the maximum length of a substring of the given string that has a roughness not exceeding .
Example 1
Example 2
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.
( points): n \leq 3;
( points): n \leq 50;
( points): n \leq 700;
( points): n \leq 5\,000;
( points): n \leq 10^5;
( points): full constraints.