Find Minimum Idleness

An a/b string records the GPU used each time, and you may flip at most switchCount positions. Find the minimum possible length of the longest run of identical characters. The original explanation contains invalid characters and a wrong example whose length shrinks after the change; this site keeps the rule that each flip changes exactly one character.

输入格式

The first line is a non-empty a/b string, and the second line is switchCount. On this site the length is 1..200000 and 0≤switchCount≤length.

输出格式

Output the minimum possible length of the longest run.

样例 1

输入：

aabbbbaaaa
2

输出：

2

样例 2

输入：

aaaa
0

输出：

4

样例 3

输入：

aabb
1

输出：

2

样例说明

The answers are 2, 4, and 2; the first example can be changed to aababbaaba, keeping the length at 10 with a longest run of 2.