Minimize Length of Longest Substring

Given a binary string, flip at most k positions so that the longest run of consecutive identical characters is as short as possible, and output that minimum length.

输入格式

The input gives a binary string s and k. The full original bounds are in the statement body: 1≤|s|≤100000, 0≤k≤|s|; they must not be lost just because the Constraints section is empty.

输出格式

Output one integer answer.

样例 1

输入：

00000
2

输出：

1

样例 2

输入：

001100
1

输出：

2

样例 3

输入：

1
0

输出：

1

样例说明

The outputs of the three public examples are, in order: 1; 2; 1. They have been checked by independent enumeration or direct simulation.