Station
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
First line contains two numbers n (2 ≤ n ≤ 500000) and k (1 ≤ k ≤ 3000). 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
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.
