Cerință

Avem la dispozitie un șir $v$ de $N$ numere, un $K$ și un $C$.

Se aleg maxim $K$ subsecvențe continue disjuncte. Care este suma costurilor subsecvențelor maximă?
Costul secvenței $[i \dots j] = (v[i]+v[j])^2+C+\sum_{p=i}^{j}v[p]$, $i < j$.

Date de intrare

Pe prima linie se găsesc numerele $N$, $K$ și $C$.
Pe a doua linie este șirul $v$ de $N$ numere.

Date de ieșire

Suma costurilor maximă posibilă.

Restricții și precizări

• $1 \leq N \leq 10^5$;
• $1 \leq K \leq \left \lfloor{\frac{N}{2}}\right \rfloor$;
• $1 \leq v_i, C \leq 10^4$;
• Fiecare subsecvență aleasă trebuie să aibă cel puțin $2$ elemente.

Exemplul 1

stdin

5 2 1
2 3 1 2 1

stdout

44

Explicație

Alegem subsecvențele $[1,2]$ și $[4,5]$, costurile de $(2+3)^2+1+2+3=31$ și $(2+1)^2+1+2+1=13$, în total $44$.

Exemplul 2

stdin

10 4 6
5 7 31 8 3 19 48 6 9 5

stdout

6764