Problem Description
Guangxuan has been shopping for Chunlians during CNY. When he entered the shop, he found N Chunlians hung on the wall, from left to right. Each Chunlian had a certain value Pi.
He needs to buy C Chunlians for his family. Furthermore, due to his laziness, he wants to select the Chunlians such that no two Chunlians (including non-consecutive ones) are more than distance K apart from one another on the wall.
Help Guangxuan determine the maximum value he can obtain.
Input
The first line of input will contain three integers, N, C and K.
The second line of input will contain N integers, representing the array P.
Output
The output should contain one integer, representing the maximum value Gug can obtain.
Limits
For all subtasks: 1 ≤ C ≤ N, C - 1 ≤ K < N, 1 ≤ Pi ≤ 109.
Subtask 1 (13%): 1 ≤ N ≤ 20.
Subtask 2 (15%): 1 ≤ N ≤ 200.
Subtask 3 (17%): 1 ≤ N ≤ 1000.
Subtask 4 (12%): 1 ≤ N ≤ 300000, 1 ≤ Pi ≤ 2.
Subtask 5 (14%): 1 ≤ N ≤ 300000, 1 ≤ C ≤ 2.
Subtask 6 (29%): 1 ≤ N ≤ 300000.
Subtask 7 (0%): Sample Testcases
Sample Testcase 1
Input
5 2 3
8 1 2 3 5
Output
11
Sample Testcase 2
Input
7 3 4
5 7 1 6 3 5 9
Output
20