Selecting Elements (Hard Version)

Problem Description

You are given an integer sequence $a_1, a_2, \dots, a_n$ of length $n$.

Choose exactly $x$ elements from it, subject to:

1. Every contiguous subsequence of length $k$ in the original sequence contains at least one chosen element.
2. Under condition 1, the sum of the $x$ chosen elements should be as large as possible.

Output the maximum possible sum.

Input Format

The first line contains three integers $n, k, x$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output Format

If the requirement cannot be satisfied, output $-1$.

Otherwise, output one integer: the maximum possible sum of the chosen elements.

Sample Input 1

5 2 3
5 1 3 10 1

Sample Output 1

18

Sample Input 2

6 1 5
10 30 30 70 10 10

Sample Output 2

-1

Sample Input 3

4 3 1
1 100 1 1

Sample Output 3

100

Constraints

For all test cases, $1 \le k, x \le n \le 2500$ and $1 \le a_i \le 10^9$.