{"raw_statement":[{"iden":"statement","content":"A 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_.\n\nFor 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_.\n\nDetermine 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_."},{"iden":"input","content":"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.\n\nThe 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."},{"iden":"output","content":"If the frog can not reach the home, print _\\-1_.\n\nIn 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."},{"iden":"examples","content":"Input\n\n8 4\n10010101\n\nOutput\n\n2\n\nInput\n\n4 2\n1001\n\nOutput\n\n\\-1\n\nInput\n\n8 4\n11100101\n\nOutput\n\n3\n\nInput\n\n12 3\n101111100101\n\nOutput\n\n4"},{"iden":"note","content":"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).\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"一只青蛙生活在数轴 #cf_span[Ox] 上，需要到达位于点 #cf_span[n] 的家。它从点 #cf_span[1] 出发。青蛙每次可以向右跳跃不超过 #cf_span[d] 的距离。因此，当它从点 #cf_span[x] 跳跃后，可以到达点 #cf_span[x + a]，其中 #cf_span[a] 是一个介于 #cf_span[1] 到 #cf_span[d] 之间的整数。\n\n对于从 #cf_span[1] 到 #cf_span[n] 的每个点，已知该点是否有睡莲。青蛙只能落在有睡莲的点上。保证点 #cf_span[1] 和点 #cf_span[n] 上都有睡莲。\n\n求青蛙从点 #cf_span[1] 到达点 #cf_span[n] 所需的最少跳跃次数。假设青蛙初始位于点 #cf_span[1]。如果青蛙无法到达家，请输出 _-1_。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[d]（#cf_span[2 ≤ n ≤ 100]，#cf_span[1 ≤ d ≤ n - 1]）——分别表示青蛙想要到达的点和青蛙跳跃的最大长度。第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]，由 0 和 1 组成。如果字符串 #cf_span[s] 的某个字符为 0，则对应点没有睡莲；否则，该点有睡莲。保证字符串 #cf_span[s] 的第一个和最后一个字符均为 1。"},{"iden":"output","content":"如果青蛙无法到达家，请输出 _-1_。否则，输出青蛙从点 #cf_span[1] 到达点 #cf_span[n] 所需的最少跳跃次数。"},{"iden":"examples","content":"输入8 410010101输出2输入4 21001输出-1输入8 411100101输出3输入12 3101111100101输出4"},{"iden":"note","content":"在第一个例子中，青蛙可以通过两次跳跃到达家：第一次从点 #cf_span[1] 跳到点 #cf_span[4]（跳跃长度为三），第二次从点 #cf_span[4] 跳到点 #cf_span[8]（跳跃长度为四）。在第二个例子中，青蛙无法到达家，因为要到达家需要跳跃距离为三，但其最大跳跃长度仅为二。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, d \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 100 $, $ 1 \\leq d \\leq n-1 $.  \nLet $ s \\in \\{0,1\\}^n $ be a binary string where $ s[i] = 1 $ iff a lily flower is present at position $ i+1 $ (1-indexed).  \nGiven: $ s[0] = 1 $ and $ s[n-1] = 1 $.\n\nLet $ V = \\{ i \\in \\{1, \\dots, n\\} \\mid s[i-1] = 1 \\} $ be the set of positions with lilies.\n\n**Constraints**  \nThe frog starts at position $ 1 $ and must reach position $ n $.  \nFrom any position $ x \\in V $, the frog may jump to position $ y \\in V $ iff $ 1 \\leq y - x \\leq d $.\n\n**Objective**  \nFind the minimum number of jumps to reach $ n $ from $ 1 $, using only positions in $ V $.  \nIf no such path exists, output $ -1 $.","simple_statement":null,"has_page_source":false}