Cerința

Se dă un șir de N numere întregi indexat de la 1. Să se afle subșirul de sumă maximă format din T elemente astfel încât oricare 2 elemente consecutive ale acestuia să se afle la distanță cel puțin 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 ≤ 3500
• 1 ≤ T ≤ 1000
• 1 ≤ K ≤ 25
• 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
• se garantează că va exista mereu soluție pentru datele de test folosite
• pentru teste în valoare de 30 de puncte N ≤ 300 și T ≤ 50

Exemplu:

Intrare

6 3 2
1 -1 2 -4 5 6

Ieșire

9

Explicație

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