Team Formation

In each round, choose the highest score from the union of the first k people and the last k people of the remaining sequence; when the windows overlap, each person counts only once. Ties go to the smallest original index. Remove the chosen person and add their score to the total, until team_size people have been chosen.

输入格式

n team_size k, with 1≤n≤2000 and 1≤team_size,k≤n; followed by n scores (−10⁹..10⁹). The ranges of n and the scores are site supplements.

输出格式

Output the total score, using a 64-bit integer.

样例 1

输入：

9 3 4
17 12 10 2 7 2 11 20 8

输出：

49

样例 2

输入：

4 3 1
5 5 5 5

输出：

15

样例 3

输入：

3 2 2
-1 -8 -2

输出：

-3