Ếch nhảy K bước

Bối cảnh và bài toán

Có n trạm độ cao h_i. Từ i có thể nhảy đến một trong K trạm kế tiếp; chi phí là độ chênh độ cao.

Yêu cầu

Tính chi phí nhỏ nhất đến trạm n.

Input

Dòng 1: n K. Dòng 2: các độ cao.

Output

In chi phí nhỏ nhất.

Ràng buộc

• 2 <= n <= 10^5
• 1 <= K <= 100
• 1 <= h_i <= 10^9

Chấm điểm

Ví dụ 1

Input

5 3
10 30 40 50 20

Output

30

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

3 1
10 20 10

Output

20

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from AtCoder Educational DP Contest B – Frog 2. Bản FULLHOUSE DEV đã biên tập bối cảnh/format và ràng buộc khi cần để khớp scope-lock của khóa học.