Ếch 2 (Frog 2)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ phiến đá có độ cao $h_i$. Từ đá $i$, ếch có thể nhảy tới bất kỳ đá nào trong $i+1,\ldots,i+K$. Chi phí nhảy từ $i$ tới $j$ là $|h_i-h_j|$. Hãy tìm chi phí nhỏ nhất để đi từ đá 1 tới đá $N$.

Input

Dòng 1 chứa $N$ và $K$. Dòng 2 chứa $N$ số nguyên $h_1,\ldots,h_N$.

Output

In chi phí nhỏ nhất.

Subtask

• Subtask 1 — 20 điểm: 2 <= N <= 20; 1 <= K <= 5. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: 2 <= N <= 2000; 1 <= K <= 30. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 2 <= N <= 100000; 1 <= K <= 100; 1 <= h_i <= 10000. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

5 3
10 30 40 50 20

Output

30

Giải thích

Có thể đi $1\to2\to5$, chi phí $20+10=30$ và không có phương án nào rẻ hơn.