Sharmeen the little girl recently learned about string. She found a long string from a book. The string contains characters from ‘a’ to ‘z’, ‘0’ to ‘9’ and commas(,). Now she wonder what will be the length of the largest substring of this string which will contain at most K commas? As she is not a programmer, can you do it for her?

Input

You will be given a string of length n( 1 <= n <= 10^5) in the first line.

In the second line you will be given an integer K( 0 <= K <= n ), which is the maximum number of commas allowed in the expected substring.

Output

Output the length of the largest substring.

Constrain:

1 <= n <= 10^5

0 <= k <= n

Example

Input:
a,b,a0,3hg,0,,,sdfghijfh06
3

Output:
15

Explanation:

The expected substring is “0,,,sdfghijfh06” which has a length of 15.
There may be more than one optimal substring, but you don’t need to think about that, you have to just print the length of any optimal substring.