Farmer Ron tại Colorado làm khu trượt tuyết cho bò, ngân sách chỉ cho một thang. Đường ray đơn nối trụ bê tông đầu với cuối qua trụ giữa, mỗi trụ cao0 so với đất. Thép thẳng nối từng cặp kề nhau phải ở trên đất tại mọi điểm.

Tiết kiệm, FR giảm tối đa trụ. Khảo sát $N$ mảnh đất đều $(2 \le N \le 5,000)$, ghi chiều cao nguyên $H$ $(0 \le H \le 1,000,000,000)$. An toàn đòi khoảng cách trụ kề không quá $K$ đơn vị $(1 \le K \le N - 1)$. Thép cứng tạo đường thẳng.

Tìm ít trụ nhất: thép hoàn toàn trên hoặc tiếp xúc đất, khoảng cách ngang kề không quá $K$, trụ trên mảnh đầu và cuối.

Dữ liệu vào

• Dòng $1$: hai số nguyên cách dấu cách $N$, $K$.
• Các dòng $2..N+1$: dòng $i+1$ có chiều cao nguyên mảnh $i$.

Dữ liệu ra

• Dòng $1$: số nguyên, ít trụ nhất theo điều kiện.

Ví dụ

Dữ liệu vào 1

13 4
0
1
0
2
4
6
8
6
8
8
9
11
12

Dữ liệu ra 1

5

Ghi chú

5 trụ tại1, 5, 7, 9, 13. Thép tiếp xúc đất tại4 nơi:1–5, 5–7, 7–9, 12–13.

4 trụ tại1, 5, 9, 13 làm thép dưới đất5–9. Tại1, 7, 13 thép trên đất nhưng7 và13 cách ngang quá4. Không có nghiệm dưới5 trụ với khoảng cách kề không quá4.

Nguồn nguyên văn: https://github.com/ivankra/acm/blob/master/usaco/MAR06/prob/gold-en.htm

Tác giả bài toán: Adam Rosenfield, 2004