rarsum

Problem Description

Rar the cat is actually a programmer. So he has a programming problem for you guys to solve: Max Sum. However, he finds this too easy and classic to be used as a selection test problem, especially for RI programmers! They need some challenge, don't they? Therefore, he has made a variant of max sum, known as the Rar Sum.

Rar Sum is extremely similar to Max Sum. You are provided with a list of N integers, whereby you have to find out the largest contiguous sub-array with the largest sum. However, the challenge Rar has added is that the sub-array length must be a multiple of K and also must have at least L elements.

Input

You are to input from standard input.

The first line consists of 3 integers, in the following order N, K, L

The second line consists of N space separated integers, the list of N integers in which you have to find the Rar Sum from.

Output

You are to output to standard output.

Output a single integer, the sum value of the largest contiguous sub-array with the largest sum that has at least L elements and its length is a multiple of K.

Do note that the sub-array can be of length 0 if L is 0.

Limits

All the numbers in the provided list of N integers will be in the range of -1000 to 1000 unless otherwise stated in the subtasks (Eg. Subtask 1, 2)

The lowest multiple of K, that is larger than L is guaranteed to be not larger than N.

Subtask 1 (2%): N ≤ 100, K = 1, L = 0. All numbers in the list of N integers are guaranteed to be positive. (There are basically no restrictions on sub-array length)

Subtask 2 (3%): N ≤ 100, KN, L = 0. All numbers in the list of N integers are guaranteed to be positive.

Subtask 3 (6%): N ≤ 1000, K = 1, L = 0. (There are basically no restrictions on sub-array length)

Subtask 4 (12%): N ≤ 1000000, K = 1, L = 0. (There are basically no restrictions on sub-array length)

Subtask 5 (9%): N ≤ 1000, KN, L = 0.

Subtask 6 (13%): N ≤ 1000000, KN, L = 0.

Subtask 7 (9%): N ≤ 1000, K = 1, LN.

Subtask 8 (13%): N ≤ 1000000, K = 1, LN.

Subtask 9 (12%): N ≤ 1000, KN, LN.

Subtask 10 (21%): N ≤ 1000000, KN, LN.

Subtask 11 (0%): As per sample testcases.

Sample Testcase 1

Input:

10 1 0
1 2 3 4 5 6 7 8 9 10

Output:

55

The Rar Sum for this case is the summation of all the integers in the provided array.

Sample Testcase 2

This testcase adheres to the limits of subtask 2, 5, 6, 9, 10 only.

Input:

10 4 0
1 2 3 4 5 6 7 8 9 10

Output:

52

The Rar Sum for this case is the summation of all the integers except the first two, since the length of the subarray must be a multiple of 4.

Sample Testcase 3

This testcase adheres to the limits of subtask 3 to 10 only.

Input:

10 1 0
7 -12 8 -9 -3 20 -1 -2 9 3

Output:

29

The subarray for this case is [20 -1 -2 9 3].

Sample Testcase 4

This testcase adheres to the limits of subtask 5, 6, 9, 10 only.

Input:

10 3 0
7 -12 8 -9 -3 20 -1 -2 9 3

Output:

26

The subarray for this case is [-3 20 -1 -2 9 3].

Sample Testcase 5

This testcase adheres to the limits of subtask 7 to 10 only.

Input:

10 1 5
-1 -2 -3 -4 5 -6 -7 8 -9 -10

Output:

-4

The subarray for this case is [-4 5 -6 -7 8] since the subarray's length must be at least 5.

Sample Testcase 6

This testcase adheres to the limits of subtask 9, 10 only.

Input:

10 4 5
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10

Output:

-36

The subarray for this case is [-1 -2 -3 -4 -5 -6 -7 -8] since the subarray's length must be at least 5 and also be a multiple of 4.


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 4
Your best score: 0
Source: Raffles Cat Helping Contest 2013

Subtask Score
1 2
2 3
3 6
4 12
5 9
6 13
7 9
8 13
9 12
10 21
11 0