Mô tả bài toán
Trên bàn có $N$ viên kẹo được 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. Độ ngon của viên kẹo $i$ ($1 \le i \le N$) là $A_i$.
JOI quyết định chọn một số viên kẹo trong số $N$ viên kẹo để ăn.
Tuy nhiên, để không ăn quá nhiều kẹo, đối với bất kỳ $K$ viên kẹo liên tiếp nào, cậu chỉ ăn tối đa $2$ viên trong số đó. Nói cách khác, với mọi $j$ ($1 \le j \le N - K + 1$), trong số $K$ viên kẹo liên tiếp từ viên kẹo $j$ đến viên kẹo $j + K - 1$, số lượng viên kẹo được ăn phải không vượt quá $2$.
Dưới điều kiện này, JOI muốn tổng độ ngon của những viên kẹo mà cậu ăn là lớn nhất có thể.
Cho biết độ ngon của $N$ viên kẹo và $K$, hãy viết chương trình tìm giá trị lớn nhất của tổng độ ngon của những viên kẹo mà JOI ăn.
Ràng buộc
- $2 \le K \le N \le 3\,000$.
- $1 \le A_i \le 10^9$ ($1 \le i \le N$).
- Tất cả các giá trị đầu vào đều là số nguyên.
Subtask
- ($4$ điểm) $N \le 20$.
- ($19$ điểm) $K \le 10$.
- ($47$ điểm) $N \le 300$.
- ($30$ điểm) Không có ràng buộc bổ sung.
Dữ liệu vào
Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:
N K A_1 A_2 ... A_N
Kết quả
In ra đầu ra chuẩn trên $1$ dòng giá trị lớn nhất của tổng độ ngon của những viên kẹo mà JOI ăn.
Ví dụ
Ví dụ 1 - Dữ liệu vào
5 4 1 3 2 4 3
Ví dụ 1 - Kết quả
8
Khi JOI ăn viên kẹo $1$, viên kẹo $4$ và viên kẹo $5$, tổng độ ngon là $8$.
Trong số các cách ăn sao cho với bất kỳ $4$ viên kẹo liên tiếp nào cũng chỉ ăn tối đa $2$ viên, không có cách nào có tổng độ ngon từ $9$ trở lên, vì vậy in ra $8$.
Ví dụ này thỏa mãn các ràng buộc của tất cả các subtask.
Ví dụ 2 - Dữ liệu vào
6 3 3 7 1 5 6 4
Ví dụ 2 - Kết quả
21
Khi JOI ăn viên kẹo $1$, viên kẹo $2$, viên kẹo $4$ và viên kẹo $5$, tổng độ ngon là $21$.
Trong số các cách ăn sao cho với bất kỳ $3$ viên kẹo liên tiếp nào cũng chỉ ăn tối đa $2$ viên, không có cách nào có tổng độ ngon từ $22$ trở lên, vì vậy in ra $21$.
Ví dụ này thỏa mãn các ràng buộc của tất cả các subtask.
Ví dụ 3 - Dữ liệu vào
5 2 3 3 2 2 1
Ví dụ 3 - Kết quả
11
Ví dụ này thỏa mãn các ràng buộc của tất cả các subtask.
Ví dụ 4 - Dữ liệu vào
12 5 864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728
Ví dụ 4 - Kết quả
4427122428
Ví dụ này thỏa mãn các ràng buộc của tất cả các subtask.