Problem Description

Input Format

Inputs will be given by standard input in the following format.

$ N $ $ M $ $ K $ $ t_1 $ $ t_2 $ : $ t_N $

• At the first line, integer $ N(1≦N≦100,000) $, $ M(1≦M≦N) $, $ K(1≦K≦N) $ will be given.
• From the second line, there are $ N $ additional lines to give information about the sizes of trees. At the $ i_{th} $ line, integer $ t_i(1≦t_i≦1,000,000,000) $ will be given.

Output Format

Please print the minimum value of the maximum value of the sum of sizes of consecutive $ K $ trees, when we made the optimal cutting choice for the trees in a line.

Print a newline at the end of the output.

Sample Input and Output

Sample Input #1

6 2 3
1
5
6
2
4
3

Sample Output #1

7

Sample Input #2

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

Sample Output #2

17

Notes/Hints

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 none). 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 any $ K $ consecutive trees. More precisely, there is no $ 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 the maximum sum of sizes of any $ K $ consecutive trees.

Since the sizes 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.

Sample Explanation 1

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 $ 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 部分

见题面 Output 部分