Vào dịp lễ yêu thích, Nông dân John muốn gửi quà cho bạn bè. Vì không giỏi gói quà, ông muốn nhờ những cô bò của mình giúp đỡ. Như bạn có thể đoán, bản thân những cô bò cũng chẳng giỏi gói quà hơn là bao — một bài học mà Nông dân John sắp phải cay đắng nhận ra.

\(N\) cô bò của Nông dân John (\(1 \leq N \leq 10^4\)) đều đang đứng thành một hàng, được đánh số thuận tiện từ \(1 \ldots N\) theo thứ tự. Cô bò \(i\) có mức kỹ năng gói quà \(s_i\). Các mức kỹ năng này có thể chênh lệch khá nhiều, vì vậy FJ quyết định chia các cô bò thành những đội. Một đội có thể gồm bất kỳ nhóm nào chứa không quá \(K\) cô bò liên tiếp (\(1 \leq K \leq 10^3\)), và không cô bò nào được thuộc nhiều hơn một đội. Vì các cô bò học hỏi lẫn nhau, mức kỹ năng của mỗi cô bò trong một đội có thể được thay bằng mức kỹ năng của cô bò giỏi nhất trong đội đó.

Hãy giúp FJ xác định tổng mức kỹ năng lớn nhất có thể đạt được nếu ông lập đội một cách tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\). \(N\) dòng tiếp theo chứa mức kỹ năng của \(N\) cô bò theo thứ tự chúng đang đứng. Mỗi mức kỹ năng là một số nguyên dương không vượt quá \(10^5\).

Dữ liệu ra

In ra tổng mức kỹ năng lớn nhất mà FJ có thể đạt được bằng cách chia những nhóm bò liên tiếp thích hợp thành các đội.

Ví dụ

7 3
1
15
7
9
2
5
10

84

Nguồn

Đề bài gốc: USACO 2018 December Contest, Gold — Teamwork

Tác giả: Brian Dean