Walle

Roboțelul explorator Wall-E se deplasează pe o hartă reprezentată ca o succesiune de celule, numerotate de la $1$ la $N$. Fiecare celulă are asociat un anumit nivel de energie.

Se numește secvență o succesiune de celule de pe hartă numerotate consecutiv. Energia unei secvențe este egală cu suma nivelurilor de energie asociate celulelor din care este formată secvența.

Wall-E poate modifica nivelul de energie al unor celule respectând următoarele două conditții:

• nivelul de energie al unei celule modificate crește cu un număr natural cuprins între $1$ și $X$;
• suma tuturor valorilor cu care au crescut nivelurile de energie ale celulelor modificate este egală cu $S$.

După modificarea nivelurilor de energie, Wall-E este interesat de secvențele critice de lungime $L$.

O secvență de lungime $L$ este considerată critică dacă energia secvenței este minimă, în raport cu toate secvențele de lungime $L$ existente pe hartă.

Cerință

Determinați energia maximă a unei secvențe critice de lungime $L$, după ce Wall-E modifică convenabil nivelul de energie al unor celule, respectând condițiile din enunț.

Date de intrare

Fișierul de intrare walle.in conține pe prima linie numărul natural $N$, reprezentând numărul de celule de pe hartă. Pe a doua linie se află numerele naturale $X$, $S$ și $L$ cu semnificația din enunț. Pe ultima linie se află $N$ numere naturale, reprezentând nivelurile de energie ale celulelor de hartă în ordinea numerotării acestora. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire walle.out conține o singură linie pe care este scris răspunsul la cerință.

Restricții și precizări

• $1 \leq L \leq N \leq 10^5$
• Nivelul de energie al oricărei celule este un număr natural nenul $\leq 10^3$
• $1 \leq X \leq 10^3$
• $1 \leq S \leq 10^5$

Exemplul 1

walle.in

6
3 5 3
1 2 3 6 5 4

walle.out

11

Explicație

$N = 6, X = 3, S = 5, L = 3$. Wall-e poate modifica nivelul de energie al celulelor astfel:

• pentru celula $1$ nivelul de energie crește cu $2$;
• pentru celula $2$ nivelul de energie crește cu $1$;
• pentru celula $3$ nivelul de energie crește cu $2$.

Nivelurile de energie ale celulelor de pe hartă devin: $3$ $3$ $5$ $6$ $5$ $4$. Secvențele de lungime $L = 3$ au energia

• $3+3+5=11$
• $3+5+6=14$
• $5+6+5=16$
• $6+5+4=15$

Există o singură secvență critică de lungime $3$ și aceasta are energia $11$, aceasta fiind valoarea maximă posibilă.

Exemplul 2

walle.in

5
2 3 1
3 1 4 7 2

walle.out

3

Explicație

$N = 5, X = 2, S = 3, L = 1$. Wall-e poate modifica nivelul de energie al celulelor astfel:

• pentru celula $2$ nivelul de energie crește cu $2$;
• pentru celula $5$ nivelul de energie crește cu $1$.

Nivelurile de energie ale celulelor de pe hartă devin: $3$ $3$ $4$ $7$ $3$. Secvențele de lungime $L = 1$ sunt reprezentate de valoarea fiecărei celule, deci secvențele critice de lungime $L$ au energia $3$, aceasta fiind valoarea maximă posibilă.