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.

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.

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.

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.

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.

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.

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

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

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.

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.

Subtask | Score |
---|---|

1 | 2 |

2 | 3 |

3 | 6 |

4 | 12 |

5 | 9 |

6 | 13 |

7 | 9 |

8 | 13 |

9 | 12 |

10 | 21 |

11 | 0 |