Longest run after replacements

Problem

A label printer can change at most k letters of a word of capital letters. Print the length of the longest run of one repeated letter you can make.

Example

Input

AABABBA
1

Output

Change the A in "BABB" to B to get four B in a row.

Try the problem first. Open one hint at a time.

Hint 1

A piece can become one letter if (its length - the count of its most common letter) is at most k.

Hint 2

Shrink from the left while that is false.

Write your Python code, run it on the examples and submit it to hidden tests.