Trong ngày hội chào tân sinh viên, Đoàn Thanh niên Đại học Công nghiệp Hà Nội tổ chức trò chơi "Nhảy bậc". Trên sân kẻ ~n~ ô xếp thành một hàng, đánh số từ ~1~ đến ~n~; trong ô thứ ~i~ ghi một số nguyên ~a_i~ (có thể âm).

Người chơi xuất phát ở ô ~1~. Mỗi lượt, từ ô ~i~ đang đứng, người chơi phải nhảy về phía trước tới một trong các ô ~i+1, i+2, \ldots, i+k~ (không được nhảy vượt quá ô ~n~). Trò chơi kết thúc khi người chơi đứng ở ô ~n~; người chơi bắt buộc phải tới được đúng ô ~n~. Điểm của người chơi là tổng các số ghi trên tất cả những ô đã đứng, kể cả ô ~1~ và ô ~n~. Nếu ~n = 1~ thì trò chơi kết thúc ngay và điểm bằng ~a_1~.

Yêu cầu

Hãy tìm số điểm lớn nhất mà người chơi có thể đạt được.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~k~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~.

Kết quả ra

Ghi ra một số nguyên duy nhất là số điểm lớn nhất tìm được.

Ràng buộc

~1 \le k \le n \le 5 \cdot 10^5~; ~-10^9 \le a_i \le 10^9~.

• Subtask 1 (10% số điểm – test 01–04): ~n \le 20~;
• Subtask 2 (25% số điểm – test 05–09): ~n \le 5000~;
• Subtask 3 (15% số điểm – test 10–12): mọi ~a_i \ge 0~;
• Subtask 4 (20% số điểm – test 13–16): ~k \le 50~;
• Subtask 5 (30% số điểm – test 17–20): không có ràng buộc bổ sung.

Lưu ý: kết quả có thể âm và có thể vượt quá phạm vi kiểu số nguyên 32 bit.

Ví dụ

Dữ liệu vào mẫu 1

8 3
2 -5 -4 -1 6 -3 -2 4

Kết quả ra mẫu 1

11

Dữ liệu vào mẫu 2

4 1
3 -5 -1 -2

Kết quả ra mẫu 2

-5

Giải thích

Ví dụ thứ nhất: người chơi nhảy ~1 \to 4 \to 5 \to 8~ và được ~2 + (-1) + 6 + 4 = 11~ điểm; từ ô ~1~ chỉ nhảy được tới các ô ~2~, ~3~, ~4~ (đều ghi số âm) nên buộc phải đứng lên ít nhất một ô âm. Ví dụ thứ hai: ~k = 1~ nên người chơi phải đi qua mọi ô, điểm là ~3 - 5 - 1 - 2 = -5~.