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, K ≤ N, 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, K ≤ N, L = 0.
Subtask 6 (13%): N ≤ 1000000, K ≤ N, L = 0.
Subtask 7 (9%): N ≤ 1000, K = 1, L ≤ N.
Subtask 8 (13%): N ≤ 1000000, K = 1, L ≤ N.
Subtask 9 (12%): N ≤ 1000, K ≤ N, L ≤ N.
Subtask 10 (21%): N ≤ 1000000, K ≤ N, L ≤ N.
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.