Fruit Ninja

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description


Fruit Ninja is a juicy action game enjoyed by millions of players around the world, with squishy, splat and satisfying fruit carnage! Become the ultimate bringer of sweet, tasty destruction with every slash.
Ali is very good at this game. He can cut every single fruit accurately if he wants. But after playing a long time, he became so tired that he cannot cut more than K fruit among any consecutively M fruit. But he also enjoys watching the fruit carnage, especially the one with big fruits. So he wants to maximum the total weight of the cut fruit.

Input

The input consists several testcases.
The first line contains three integer N, M, K (1 <= K <= M <= N <= 1000). N is the number of fruit, while M, K are described in the problem.
The second line contains N integers W1 to Wn (1 <= Wi <= 10000), and Wi represents the i-th fruit’s price.

Output

Print a real number, the maximum total weight of the cut fruit.

Sample Input

10 5 3 4 4 4 6 6 6 6 6 4 4

Sample Output

30

Hint

lcy

Source

2011 Alibaba-Cup Campus Contest

提交代码