Testing Round 14 (Unrated) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

dp

greedy

implementation

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. The Way to Home

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA frog lives on the axis *Ox* and needs to reach home which is in the point *n*. She starts from the point 1. The frog can jump to the right at a distance not more than *d*. So, after she jumped from the point *x* she can reach the point *x* + *a*, where *a* is an integer from 1 to *d*.

For each point from 1 to *n* is known if there is a lily flower in it. The frog can jump only in points with a lilies. Guaranteed that there are lilies in the points 1 and *n*.

Determine the minimal number of jumps that the frog needs to reach home which is in the point *n* from the point 1. Consider that initially the frog is in the point 1. If the frog can not reach home, print -1.

Input

The first line contains two integers *n* and *d* (2 ≤ *n* ≤ 100, 1 ≤ *d* ≤ *n* - 1) — the point, which the frog wants to reach, and the maximal length of the frog jump.

The second line contains a string *s* of length *n*, consisting of zeros and ones. If a character of the string *s* equals to zero, then in the corresponding point there is no lily flower. In the other case, in the corresponding point there is a lily flower. Guaranteed that the first and the last characters of the string *s* equal to one.

Output

If the frog can not reach the home, print -1.

In the other case, print the minimal number of jumps that the frog needs to reach the home which is in the point *n* from the point 1.

Examples

Input

8 4

10010101

Output

2

Input

4 2

1001

Output

-1

Input

8 4

11100101

Output

3

Input

12 3

101111100101

Output

4

Note

In the first example the from can reach home in two jumps: the first jump from the point 1 to the point 4 (the length of the jump is three), and the second jump from the point 4 to the point 8 (the length of the jump is four).

In the second example the frog can not reach home, because to make it she need to jump on a distance three, but the maximum length of her jump equals to two.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2023 19:36:49 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|