Đăng lại ảnh mèo (bản khó)

Vova có $n$ bức ảnh xếp thành một hàng, bức ảnh thứ $i$ có độ đẹp $a_i$.

Vova muốn đăng lại (repost) đúng $x$ bức ảnh sao cho thỏa mãn cả hai điều kiện:

• Trong mọi dãy gồm $k$ bức ảnh liên tiếp bất kỳ, có ít nhất một bức được đăng lại.
• Tổng độ đẹp của các bức ảnh được đăng lại là lớn nhất có thể.

Nói cách khác, giữa hai bức được đăng lại liên tiếp (kể cả tính từ đầu hàng đến bức đầu tiên và từ bức cuối cùng đến cuối hàng) không được có $k$ bức liên tiếp nào mà không có bức nào được đăng.

Hãy tính tổng độ đẹp lớn nhất có thể, hoặc cho biết không tồn tại cách chọn nào thỏa mãn.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $k$, $x$: số bức ảnh, độ dài đoạn tối thiểu cần có một bức được đăng lại, và số bức ảnh phải đăng lại.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$: độ đẹp của các bức ảnh.

Dữ liệu ra

In ra một số nguyên là tổng độ đẹp lớn nhất có thể, hoặc $-1$ nếu không có cách chọn nào thỏa mãn các điều kiện.

Ràng buộc

• $1\le k,x\le n\le 5000$
• $1\le a_i\le {10}^9$

Ví dụ