Cắt cỏ (Mowing the Lawn G)

Nguồn: Luogu

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

Đề bài

Có $N$ con bò xếp thành hàng, bò $i$ có hiệu suất $E_i$. Chọn một số bò sao cho không có quá $K$ con bò được chọn liên tiếp. Hãy tối đa hóa tổng hiệu suất.

Input

Dòng đầu chứa $N,K$. $N$ dòng tiếp theo, mỗi dòng chứa một số $E_i$.

Output

In tổng hiệu suất lớn nhất.

Subtask

• Subtask 1 (20%): $1 \le N \le 2000$.
• Subtask 2 (30%): $1 \le N \le 2\cdot 10^4$.
• Subtask 3 (50%): $1 \le N \le 10^5$.

Toàn bộ dữ liệu tuân theo: $1 \le N \le 10^5$, $1 \le K \le N$, $0 \le E_i \le 10^9$.

Ví dụ

Input

5 2
1
2
3
4
5

Output

12

Giải thích

Không được chọn hơn hai bò liên tiếp. Có thể bỏ bò hiệu suất $3$ và chọn $1,2,4,5$, tổng bằng $12$.