Gian hàng (Circular Stalls)

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

Đề bài

Có $N$ gian hàng được bố trí thành một vòng tròn. Gian hàng thứ $i$ mang lại lợi nhuận $A_i$ nếu được chọn.

Không được chọn hai gian hàng kề nhau trên vòng tròn; do đó gian hàng $1$ và gian hàng $N$ cũng được xem là kề nhau.

Hãy chọn đúng $K$ gian hàng sao cho không có hai gian hàng được chọn kề nhau và tổng lợi nhuận là lớn nhất.

Input

• Dòng đầu chứa hai số nguyên $N$ và $K$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In ra một số nguyên duy nhất là tổng lợi nhuận lớn nhất.

Subtask

• Subtask 1 (33.3333%): $2\le N\le 25$, $1\le K\le 60$, $2K\le N$, $|A_i|\le 10^9$.
• Subtask 2 (26.6667%): $2\le N\le 2000$, $1\le K\le 20$, $2K\le N$, $|A_i|\le 10^9$.
• Subtask 3 (40%): $2\le N\le 2\times10^5$, $1\le K\le 60$, $2K\le N$, $|A_i|\le 10^9$.

Điều kiện $2K\le N$ bảo đảm luôn tồn tại ít nhất một cách chọn đúng $K$ gian hàng mà không có hai gian hàng kề nhau.

Ví dụ

Ví dụ 1

Input

5 2
5 1 4 10 3

Output

15

Giải thích

Chọn gian hàng $1$ và $4$. Hai gian hàng không kề nhau và tổng lợi nhuận là $5+10=15$.

Ví dụ 2

Input

4 2
-1 -2 -3 -4

Output

-4

Giải thích

Phải chọn đúng $2$ gian hàng. Chọn gian hàng $1$ và $3$ cho tổng $-1+(-3)=-4$, là lớn nhất.