Làm việc nhóm (Teamwork)

Nguồn: USACO

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

Đề bài

Có $N$ học sinh với mức kỹ năng. Chia dãy theo thứ tự thành các nhóm liên tiếp, mỗi nhóm có nhiều nhất $K$ người. Điểm của nhóm bằng số người nhân kỹ năng lớn nhất trong nhóm. Hãy tối đa hóa tổng điểm.

Input

Dòng đầu chứa $N,K$. Dòng hai chứa $N$ mức kỹ năng.

Output

In tổng điểm lớn nhất.

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

5 2
10 20 30 40 50

Output

170

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.