#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 2 | 2 | 1s | 64MB | Minimum |

2 | 3 | 5 | 1s | 64MB | Minimum |

3 | 6 | 10 | 1s | 64MB | Minimum |

4 | 12 | 10 | 1s | 64MB | Minimum |

5 | 9 | 10 | 1s | 64MB | Minimum |

6 | 13 | 10 | 1s | 64MB | Minimum |

7 | 9 | 10 | 1s | 64MB | Minimum |

8 | 13 | 10 | 1s | 64MB | Minimum |

9 | 12 | 10 | 1s | 64MB | Minimum |

10 | 21 | 10 | 1s | 64MB | Minimum |

11 | 0 | 6 | 1s | 64MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o rarsum -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512