Problem

Wolf Sothe owns a long land in the jungle. In this linear land, $N$ trees grow at regular intervals. The size of the $i_{th}$ tree from one end is given as $t_i$.

Inside the jungle it is dark because trees obstruct sunlight. In order to let sunlight shine into the jungle, Wolf Sothe considers cutting some of the $N$ trees (or cutting no one). More specifically, trees will be cut with the following rules.

• Up to $M$ trees can be cut (no more than $M$).
• Considering the impact on the surrounding ecosystem, it is not allowed to cut two or more trees in arbitrary $K$ consecutive trees. More precisely, there is not $i(1≦i≦N-K+1)$ such that $2$ or more trees are cut in the $i_{th}$, $(i + 1)_{th}$, ......, $(i + K-1)_{th}$ trees from one end.
• If Wolf Sothe cuts the $i_{th}$ tree from one end, the size of the tree $t_i$ becomes $0$.
• We want the maximum value of the sum of sizes of $K$ consecutive trees to be as small as possible. Namely, we want to minimize .

Since the size of the $N$ trees and $M$, $K$ have been given, when we make the optimal cutting choice for the trees, please obtain the minimum value of the maximum value of the sum of sizes of consecutive $K$ trees.

Input Example 1Copy

6 2 3
1
5
6
2
4
3

Output Example 1Copy

7

If Wolf Sothe cuts the $3_{rd}$ and $6_{th}$ tree, the minimum value of the maximum value of the sum of sizes of consecutive $3$ consecutive trees will be obtained when it is for the $2_{nd}$, $3_{rd}$, $4_{th}$ tree. The sum of sizes is $5+0+2=7$.

Input Example 2Copy

10 3 4
3
14
1
5
9
2
6
5
3
5

Output Example 2Copy

17