suxumetre

Time limit: 1.5s Memory limit: 256MB Input: Output:

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

Sux receives an array AA of NN elements as a gift from his grandfather. One day, he goes on a mountain trip with his K1K−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 KK disjoint and non-empty subarrays so that each of his K1K−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, NN, KK, and MM. The second line contains NN 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 KK subarrays: A1,A2,A3,,AkA_1, A_2, A_3, \ldots , A_k, then the cumulative weight is i=1Kgreutate(Ai)\displaystyle \sum_{i=1}^{K} greutate(A_i).
  • The legend says that even now, the tests for joingraf are not ready.
# Score Constraints
1 10 N10,K10,M10N \leq 10, K \leq 10, M \leq 10
2 30 N100,K100,M30N \leq 100, K \leq 100, M \leq 30
3 10 N1500,K100,M2N \leq 1500, K \leq 100, M \leq 2
4 50 N5000,KN,M30N \leq 5000, K \leq N, M \leq 30

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)(1, 2) and (3,4,5,6)(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)++sp(3,6)=72sp(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)(1, 2, 3) and (4,5,6)(4, 5, 6), we get a total weight of 6262.

Example 2

stdin

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

stdout

30

Log in or sign up to be able to send submissions!