Chọn quà

Vì đạt giải cao trong đợt thi học sinh giỏi cấp tỉnh, cô giáo H muốn thưởng cho An một phần thưởng đặc biệt như sau: Cô có $N$ món quà xếp thành một hàng, món quà thứ $i$ có giá trị là $a_i$, cô giáo yêu cầu An chọn các món quà sao cho:

• Không quá $k$ món liên tiếp (trong hàng không có $k+1$ món quà đứng liền nhau mà đều được chọn);
• Tổng giá trị của các món quà là lớn nhất.

Yêu cầu: Hãy viết chương trình giúp An xác định tổng giá trị các món quà lớn nhất mà An có thể nhận được.

Dữ liệu vào

• Dòng đầu chứa $2$ số nguyên $N$ và $k$ $(1\le k\le N\le {10}^6)$.
• Dòng tiếp theo chứa dãy số nguyên: $a_1,a_2,\dots ,a_N$ $(1\le a_i\le {10}^9)$.

Các số trên đề bài cách nhau một dấu cách.

Dữ liệu ra

Gồm một số nguyên là tổng giá trị lớn nhất mà An có thể nhận được.

Ràng buộc

• $1\le k\le N\le {10}^6$.
• $1\le a_i\le {10}^9$.

Subtasks

• $40\%$ số test: $1\le k\le N\le 20$.
• $30\%$ số test: $k=2$, $N\le 20$.
• $20\%$ số test: $k=2$, $N\le {10}^6$.
• $10\%$ số test còn lại: $k=N$, $N\le {10}^6$.

Ví dụ