Trên bàn có \(N\) viên kẹo xếp thành một hàng ngang, được đánh số từ \(1\) đến \(N\) theo thứ tự từ trái sang phải. Viên kẹo \(i\) (\(1 \le i \le N\)) có độ ngon là \(A_i\).

JOI quyết định chọn một số viên trong \(N\) viên kẹo để ăn. Tuy nhiên, để không ăn quá nhiều, trong bất kỳ \(K\) viên kẹo liên tiếp nào, JOI chỉ được ăn nhiều nhất \(2\) viên. Cụ thể, với mọi \(j\) (\(1 \le j \le N-K+1\)), số viên được ăn trong các viên từ \(j\) đến \(j+K-1\) phải không vượt quá \(2\).

Với điều kiện đó, JOI muốn tổng độ ngon của các viên kẹo được ăn lớn nhất có thể. Cho độ ngon của \(N\) viên kẹo và giá trị \(K\), hãy tìm tổng độ ngon lớn nhất mà JOI có thể đạt được.

Dữ liệu vào

Dữ liệu vào có dạng:

N K
A_1 A_2 ... A_N

Dữ liệu ra

In ra một dòng chứa tổng độ ngon lớn nhất của các viên kẹo mà JOI có thể ăn.

Ràng buộc

• \(2 \le K \le N \le 3000\).
• \(1 \le A_i \le 10^9\) (\(1 \le i \le N\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. 4 điểm: \(N \le 20\).
2. 19 điểm: \(K \le 10\).
3. 47 điểm: \(N \le 300\).
4. 30 điểm: Không có ràng buộc bổ sung.

Ví dụ

5 4
1 3 2 4 3

8

6 3
3 7 1 5 6 4

21

5 2
3 3 2 2 1

11

12 5
864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728

4427122428

Nguồn

Đề bài Candies 2, JOI 2021/2022, vòng loại thứ hai, bài 4 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.