Trò chơi nhảy VI (Jump Game VI)

Nguồn: LeetCode

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

Đề bài

Bạn đứng tại vị trí $0$ của dãy. Mỗi bước được nhảy tiến từ $1$ đến $k$ vị trí và phải kết thúc tại vị trí $n-1$. Điểm số là tổng các giá trị ở mọi vị trí đã ghé qua. Hãy tìm điểm lớn nhất.

Input

Dòng đầu chứa $n,k$. Dòng thứ hai chứa $n$ số nguyên.

Output

In điểm số lớn nhất có thể đạt được.

Subtask

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

Toàn bộ dữ liệu tuân theo: $1 \le n,k \le 10^5$, $k \le n$, $-10^4 \le a_i \le 10^4$.

Ví dụ

Input

6 2
1 -1 -2 4 -7 3

Output

7

Giải thích

Một đường đi tối ưu ghé các giá trị $1,-1,4,3$, tổng bằng $7$.