Problem 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
