eolymp
bolt
Try our new interface for solving problems
Problems

Station

Station

Time limit 1 second
Memory limit 128 MiB

Taiwan has a rail system that connects all train stations. The rail system has stations indexed from 0 to n - 1. Every two adjacent train stations are 1 kilometer apart, and some stations have lodge service. Also the first and the last stations do have lodge service.

Jian-Jia wants to travel through Taiwan along this railway system. Jian-Jia will start from the first station and stops at the last station. Since Jian-Jia bought a discount ticket, he can only travel at most k kilometers per day. In addition, Jian-Jia only wishes to stop at stations that have lodge service. Please determine the minimum number of days for Jian-Jia to travel from the first to the last station.

Given the locations of all stations with lodge service and the limit k, determine whether it is possible for Jian-Jia to travel from the first station to the last station, and if possible, the minimum number of days for Jian-Jia to do so.

Input data

First line contains two numbers n (2n500000) and k (1k3000). Second line is an array lodge indicating whether a station has lodge service. For example, if station has lodge service then lodge[i] will be 1 and 0 otherwise. We assume that both lodge[0] and lodge[n-1] are 1.

Output data

Print the minimum number of days for Jian-Jia to travel from the first station to the last station if possible. If not possible then print -1.

Example

Consider the third test case. We assume that there are 10 stations, and station 0, 1, 2, 3, 4, 6, 7, 9 have lodge service. Let k be 4, i.e., Jian-Jia can only travel 4 kilometers per day, then he needs at least 3 days to travel from station 0 to 9. For example, he can move from station 0 to station 3 in the first day, station 3 to 7 in the second day, and station 7 to 9 in the third day. If k is 1 then it is impossible to travel from the first station to the last station.

prb7758.gif

Examples

Input example #1
11 3
1 1 0 0 1 1 0 1 0 0 1
Output example #1
4
Input example #2
13 3
1 0 0 0 1 0 0 1 0 0 0 0 1
Output example #2
-1
Input example #3
10 4
1 1 1 1 1 0 1 1 0 1
Output example #3
3

Source 2014 IOI, Practice Day 0