suxumetre

"ok, enunturile la muxusetre si 3secv sunt gata, ma ocup FR ACUM de testele la joingraf."

Pentru un șir $A$ de $N$ numere definim greutatea acestuia $greutate(A) = \displaystyle \sum_{i \leq j}^{N} sp(i,j)$, unde $sp(i,j) = \left( \displaystyle \sum_{k = i}^{j} A[k] \right) \mod M$

Sux primește un vector $A$ de $N$ elemente în dar de la bunicul său. Acesta într-o zi pleacă în excursie la munte cu cei $K−1$ prieteni ai lui, și fiind foarte atașat de cadoul primit, decide să ia șirul cu el. Ajunși la poalele muntelui , observă cu tristețe că el nu poate să care singur șirul până în vârful muntelui, deoarece este prea greu. Așadar, Sux, încearcă să împartă șirul în $K$ secvențe disjuncte și nevide astfel încât fiecare din cei $K − 1$ prieteni să primească exact o secvență (rămânându-i lui Sux exact una) și suma greutaților cumulate să fie minimă.

Cerință

Ajutați-l pe Sux să calculeze valoarea minimă.

Date de intrare

Pe prima linie se găsesc trei numere întregi, $N$, $K$ și $M$.
Pe a doua linie se află $N$ numere separate prin cate un spațiu.

Date de ieșire

Pe prima linie se va găsi un număr reprezentând raspunsul problemei.

Restricții și precizări

• Dacă Sux împarte vectorul în $K$ secvențe : $A_1, A_2, A_3, ... , A_k$, atunci greutatea cumulată este $\displaystyle \sum_{i=1}^{K} greutate(A_i)$.
• Legenda spune că nici până acum nu sunt gata testele la joingraf.

Exemplul 1

stdin

6 2 9
2 6 7 1 8 7 

stdout

62

Explicație

Dacă alegem să împărțim vectorul în secvențele $(1, 2)$ și $(3, 4, 5, 6)$ atunci greutatea totală va fi $sp(1,1) + sp(2,2) + sp(1,2) + sp(3,3) + sp(4,4) + ... + sp(3,6) = 72$
Însa dacă împarțim vectorul în secvențele $(1, 2, 3)$ și $(4, 5, 6)$ obținem greutatea totală $62$.

Exemplul 2

stdin

10 5 6
57258 79818 45081 80878 97780 67843 78314 38965 34431 9159 

stdout

30