Cerința

După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N, K și W apoi un vector cu N elemente, din acest vector care este suma maximă a unei secvențe (elemente adiacente) de lungime cel puțin K și cel mult W. A zis să vă întrebe pe voi cum se face.

Date de intrare

Fișierul de intrare ksum2.in conține pe prima linie numerele N, K și W, pe următoarea linie N elemente întregi reprezentând elementele vectorului.

Date de ieșire

Fișierul de ieșire ksum2.out va conține pe prima linie numărul S, reprezentând suma maximă a unei secvențe (elemente adiacente) din vector de lungime cel puțin K și cel mult W.

Restricții și precizări

• 1 ≤ K ≤ W ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi din intervalul [-1.000, 1.000].

Exemplu:

ksum2.in

6 3 4
5 4 -10 1 2 3

ksum2.out

6

Explicație

Secvența căutată este [4, 6] cu suma 1 + 2 + 3 = 6.