Description

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character.

You can perform this operation at most k times.

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

Input format:

• Line 1: String s
• Line 2: Integer k

Examples

Input:
ABAB
2

Output:
4

Input:
AABABBA
1

Output:
4

Note:

Print a single integer representing the maximum length.