You are given a strings of 0 and 1's. Now the task is to make the string consisting of only 1's. But you are allowed to perform only the following operation:

Take exactly k consecutive elements of string and change 1 to 0 and 0 to 1. Each operation takes 1 unit time so you have to determine the minimum time required to make the string of 1's only. If not possible return -1.

2 ≤ length of S ≤ 1000

Examples

Input

00010110 3

Output

3

Explanation

You can get 1 by first changing the leftmost 3 elements, getting to 11110110, then the rightmost 3, getting to 11110001, and finally the 3 left out 0's to 11111111; In 3 unit time.

Any approaches for it.