Chọn Ảnh Phủ Mọi Cửa Sổ · canuc80k2639

Có $n$ bức ảnh xếp theo một hàng; ảnh thứ $i$ có độ đẹp $a_{i}$ . Bạn phải chọn đúng $x$ ảnh.

Một cách chọn được xem là hợp lệ khi mọi đoạn gồm đúng $k$ ảnh liên tiếp đều chứa ít nhất một ảnh đã chọn. Trong số các cách hợp lệ, hãy tìm tổng độ đẹp lớn nhất của các ảnh được chọn.

Input

Dòng đầu chứa ba số nguyên $n, k, x$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Output

In tổng độ đẹp lớn nhất. Nếu không tồn tại cách chọn đúng $x$ ảnh thỏa điều kiện, in $- 1$ .

Constraints

$1 \leq k, x \leq n \leq 5000$ .
$1 \leq a_{i} \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50%$ ): $n \leq 20$ .
Subtask $2$ ( $50%$ ): Không có giới hạn bổ sung.

Example

Test 1

Input

6 3 2
4 9 1 8 2 7

Output

Giải thích: Chọn ảnh ở vị trí $2$ và $4$ . Bốn đoạn dài $3$ lần lượt là $[1, 3], [2, 4], [3, 5], [4, 6]$ ; mỗi đoạn đều chứa ít nhất một vị trí đã chọn. Tổng độ đẹp là $9 + 8 = 17$ , và không có cách hợp lệ nào đạt tổng lớn hơn.

Ý tưởng: Gọi các vị trí được chọn theo thứ tự là p_1 < p_2 < ... < p_x. Điều kiện mọi cửa sổ dài k được phủ tương đương với ba nhóm điều kiện:
Ý tưởng: p_1 ≤ k;
Ý tưởng: p_t - p_(t-1) ≤ k với mọi t ≥ 2;
Ý tưởng: p_x ≥ n-k+1.
Ý tưởng: Nếu một trong ba điều kiện sai, tồn tại ngay một đoạn dài k nằm trước vị trí đầu, giữa hai vị trí liên tiếp hoặc sau vị trí cuối mà không chứa điểm chọn. Chiều ngược lại cũng đúng.
Quy hoạch động theo số lần chọn: Với một lớp cố định t, đặt pre[j] là tổng lớn nhất khi đã chọn đúng t-1 vị trí và vị trí cuối cùng là j. Trạng thái giả j=0 có giá trị 0 trước lớp đầu tiên.
Quy hoạch động theo số lần chọn: Nếu vị trí thứ t là i, vị trí trước đó phải thuộc đoạn [i-k, i-1]. Do đó
Quy hoạch động theo số lần chọn: cur[i] = a_i + max(pre[j]) với i-k ≤ j < i.
Quy hoạch động theo số lần chọn: Khi quét i tăng dần, một deque đơn điệu duy trì giá trị lớn nhất của pre trong cửa sổ này. Mỗi chỉ số được thêm và loại nhiều nhất một lần ở mỗi lớp.
Quy hoạch động theo số lần chọn: Sau x lớp, chỉ các vị trí cuối i ≥ n-k+1 mới phủ được hậu tố. Lấy lớn nhất trên miền đó; nếu mọi trạng thái đều không thể đạt, in -1.
Chứng minh: Bổ đề tương đương cửa sổ ở trên chứng minh rằng recurrence chỉ cần kiểm soát vị trí đầu, khoảng cách liên tiếp và vị trí cuối. Theo quy nạp theo t, cur[i] xét đúng mọi lựa chọn của t-1 vị trí trước có vị trí cuối trong cửa sổ hợp lệ, nên lưu tổng tốt nhất cho đúng t vị trí kết thúc tại i. Deque chỉ thay cách tính maximum, không thay tập trạng thái được xét. Cuối cùng, lọc các vị trí thuộc n-k+1..n chính xác là điều kiện phủ hậu tố, nên giá trị lớn nhất thu được là tối ưu.
Độ phức tạp: O(n·x) thời gian và O(n) bộ nhớ.