String Streak

Given a string consisting of lowercase letters and an integer $n$, we can modify some of its characters (namely, we can change their letter to some other letter).

After all the modifications are done, we can compute the cost as follows: Let's consider a modified position to be labeled as 1 and a position which is not modified as 0. Then, we are going to find all the subarrays of 1's with maximal length (which can no longer be extended). Last but not least, for each of these subarrays, if the range of modified letters is $[L, R]$, the cost of the operation is $2^{R-L+1}$ euro.

Let's assume we have modified the letters on positions $1$, $2$, $4$, $5$ and $6$. The cost of modifying these letters will be $2^2 + 2^3 = 4 + 8 = 12$.

You have at most $n$ euro and you want to modify letters in an optimal way so that you end up having a substring containing the same letter which is as big as possible.

Now, your goal is to print the biggest possible length we can get by using this operation.

Input

On the first line you will get a string $s$ ($1 \leq |s| \leq 10^5$).
On the second line you will get an integer $n$, representing the maximum sum we can spend to modify the string ($2 \leq n \leq 10^9$).

Output

The only line of the output will contain the biggest length of any substring which can be obtained by using the described operation.

Notes

For tests worth 30 points, $1 \leq |s| \leq 100$.

Example

stdin

xabaabxab
10

stdout

9

Explanation

We can modify the letters from positions $1$, $3$, $6$, $7$ and $9$ to get nine a's in a row, with cost of $10$ euro.