Trong một căn phòng, có ~N~ cái bàn được xếp thành một hàng ngang, lần lượt từ trái sang phải. Một số bàn có điện thoại, và một số thì không. Tất cả các điện thoại đều gặp vấn đề nên điện thoại trên bàn ~i~ sẽ đổ chuông khi điện thoại trên bàn ~j~ đổ chuông, nếu bàn ~j~ cách bàn ~i~ không quá ~D~ bàn ~(|i-j| \le D)~. Bàn đầu tiên và bàn cuối cùng luôn có điện thoại. Ban đầu, điện thoại trên bàn ngoài cùng bên trái sẽ đổ chuông. Phải đặt thêm ít nhất bao nhiêu chiếc điện thoại lên các bàn khác để điện thoại trên bàn cuối cùng cũng đổ chuông?
Input
Dòng đầu tiên gồm ~2~ số nguyên dương, ~N~ ~(1 \le N \le 300\:000)~ và ~D~ ~(1 \le D \le N)~.
Dòng tiếp theo gồm ~N~ số ~0~ hoặc ~1~. Nếu số thứ ~i~ là ~1~ thì có điện thoại ở trên bàn thứ ~i~, và nếu số thứ ~i~ là ~0~ thì ngược lại.
Output
Số nguyên duy nhất là số điện thoại tối thiểu cần đặt thêm.
Sample 1
Input
4 1
1 0 1 1
Output
1
Sample 2
Input
5 2
1 0 0 0 1
Output
1
Sample 3
Input
8 2
1 1 0 0 1 0 0 1
Output
2
Subtask
- ~5~ test đầu tiên có ~N \le 20~.
- ~5~ test còn lại không có điều kiện gì thêm.
Comments