Given a string s and an integer k. Choose any character of the string and change it to any other uppercase English character. You can do this at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example

Input: s = "ABAB", k = 2 Output: 4

Explanation: Replace the two 'A's with two 'B's or two 'B' with two 'A'. The resultant string will be “AAAA” or “BBBB”. So the length longest substring with same letters will be 4 in any case.

Input: s = "AABABBA", k = 1 Output: 4

Explanation: Replace 'A' in the middle of string with 'B' to get "AABBBBA".

The substring "BBBB" has the longest repeating letters, which is 4.