#### Registered Users Only

Please login to utilize this feature.

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

## Problem Description

Peanut is playing a card game today, and in this card game, Bradley deals him a set of *N* cards in a row and lays them in a row from left to right. Each of this card contains an integer, which can be positive or negative. Bradley then asks Peanut to select up to *K* non-overlapping ranges of length up to *L*. He then has to pick up those cards and sum them. Help Peanut find the maximum sum.

## Input

The first line of input contains three integers, *N*, *K* and *L*.

The second line of input contains *N* integers, which represent the cards given to Peanut by Bradley.

## Output

Your program should output one integer, stating the maximum sum Peanut can obtain.

## Limits

1 ≤ N, K, L ≤ 3 000.Each of the integers on the cards will not have an absolute value of more than 100 000.

Subtask 1 (3%): All integers in the cards will be non-negative. L = N.

Subtask 2 (11%): K = 1, L = N.

Subtask 3 (14%): K = 1.

Subtask 4 (25%): 1 ≤ N, K, L ≤ 200.

Subtask 5 (47%): No other constraints apply.

Subtask 6 (0%): Sample testcases.

## Sample Input 1

7 1 7 5 -9 3 -2 5 5 -3

## Sample Output 1

11

## Explanation for Sample 1

5 -9 (3 -2 5 5) -3

## Sample Input 2

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

## Sample Output 2

31

## Explanation for Sample 2

1 -2 (3 4 8) -6 (7) -8 (9) -10

### Tags

### Subtasks and Limits

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

1 | 3 | 20 | 1s | 256MB | Minimum |

2 | 11 | 20 | 1s | 256MB | Minimum |

3 | 14 | 20 | 1s | 256MB | Minimum |

4 | 25 | 20 | 1s | 256MB | Minimum |

5 | 47 | 20 | 1s | 256MB | Minimum |

6 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

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