Team Formation — Alternating Front / Back Selection

In each round, pick the highest-scoring person from the union of the first k and the last k people in the remaining list, breaking ties by the smallest index; remove that person and continue until t people have been chosen. Find the sum of their scores. The original title's alternating between the two ends does not match the body text; the body text takes precedence.

输入格式

The first line contains n t k, and the second line contains n scores. This site sets 1≤t,k≤n≤100000 and 1≤score≤10⁹.

输出格式

Output the single integer required by the problem.

样例 1

输入：

5 2 1
5 1 9 2 4

输出：

9

样例 2

输入：

4 2 1
5 100 1 5

输出：

105

样例 3

输入：

3 3 2
1 2 3

输出：

6

样例说明

The answers to the three public examples are, in order: 9; 105; 6. All examples have been verified by independent small-scale enumeration or state search.