Problem 2553: H - Hai cu Crackul

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

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