## Station

### Move from one station to another

Taiwan has a rail system that connects all train stations. The rail system has n 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.

### Example

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.

### Statement

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 Format

• Line 1: two integers n and k, the number of stations and the limit;
• Line 2: `lodge[0]`, …, `lodge[n-1]`
lodge is the array indicating whether a station has lodge service. For example, if station i 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 Format

The output should contain one integer – the minimum number of days for Jian-Jia to travel from the first station to the last station if possible. If not possible, then output -1.

### Sample Input 1

```11 3
1 1 0 0 1 1 0 1 0 0 1
```

```4
```

### Sample Input 2

```13 3
1 0 0 0 1 0 0 1 0 0 0 0 1
```

```-1
```

### Subtask 1 [10% of points]

• 2 ≤ n ≤ 200, and 1 ≤ k ≤ 20

### Subtask 2 [20% of points]

• 2 ≤ n ≤ 50000, and 1 ≤ k ≤ 20

### Subtask 3 [70% of points]

• 2 ≤ n ≤ 500000, and 1 ≤ k ≤ 3000

Point Value: 7
Time Limit: 2.00s
Memory Limit: 64M