RoAlgo Contest #7 | suxumetre

For an array $A$ of $N$ numbers, we define its weight as $greutate(A) = \displaystyle \sum_{i \leq j}^{N} sp(i,j)$, where $sp(i,j) = \left( \displaystyle \sum_{k = i}^{j} A[k] \right) \mod M$.

Sux receives an array $A$ of $N$ elements as a gift from his grandfather. One day, he goes on a mountain trip with his $K−1$ friends. Being very attached to the gift, he decides to take the array with him. Upon reaching the base of the mountain, he realizes with sadness that he cannot carry the array alone to the top because it is too heavy. Therefore, Sux tries to divide the array into $K$ disjoint and non-empty subarrays so that each of his $K−1$ friends receives exactly one subarray (leaving Sux with exactly one) and the sum of the cumulative weights is minimized.

Task

Help Sux calculate the minimum value.

Input data

The first line of the input contains three integers, $N$, $K$, and $M$. The second line contains $N$ numbers separated by spaces.

Output data

The first line contains a number representing the answer to the problem.

Constraints and clarifications

• If Sux divides the array into $K$ subarrays: $A_1, A_2, A_3, \ldots , A_k$, then the cumulative weight is $\displaystyle \sum_{i=1}^{K} greutate(A_i)$.
• The legend says that even now, the tests for joingraf are not ready.

Example 1

stdin

6 2 9
2 6 7 1 8 7 

stdout

62

Explanation

If we choose to split the array into subarrays $(1, 2)$ and $(3, 4, 5, 6)$ then the total weight will be $sp(1,1) + sp(2,2) + sp(1,2) + sp(3,3) + sp(4,4) + \ldots + sp(3,6) = 72$.
However, if we split the array into subarrays $(1, 2, 3)$ and $(4, 5, 6)$, we get a total weight of $62$.

Example 2

stdin

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

stdout

30