Cerința

Se dă un șir de N numere întregi indexat de la 1. Să se afle suma maximă a unui subșir format din T elemente astfel încât oricare 2 elemente consecutive ale acestuia să se afle la distanță cel mult K în șirul dat (distanța dintre elementele de pe pozițiile i și j, i < j, este j - i).

Date de intrare

Programul citește de la tastatură pe prima linie numerele N T K, iar apoi N numere întregi, separate prin spații.

Date de ieșire

Programul va afișa pe ecran valoarea sumei maxime găsite.

Restricții și precizări

• 1 ≤ N ≤ 4500
• 1 ≤ T ≤ N
• 1 ≤ K ≤ 1000
• cele N numere citite vor fi din intervalul [-1.000.000.000, 1.000.000.000]
• se numește subșir al unui șir o succesiune de elemente(nu neapărat consecutive în acesta) ale acestuia, considerate în ordinea în care apar în șir
• pentru teste în valoare de 50 de puncte N ≤ 1500, T ≤ 300, K ≤ 100

Exemplu:

Intrare

6 3 2
1 -1 2 -4 5 6

Ieșire

13

Explicație

Singurul subșir care respectă condițiile din enunț pentru care se obține suma maximă 13 este cel format din elementele de pe pozițiile 3, 5 și 6.