Hide

Problem C
Smooth Array

/problems/smootharray/file/statement/en/img-0001.png
Image of an array of smoothies by Silvia.
We always hope things in our lives will run smoothly, and having smooth arrays may help. An array $A$ of $N$ non-negative integers is $K_ S$-smooth if the sum of every set of $K$ consecutive integers is exactly $S$. Unfortunately, not all arrays are $K_ S$-smooth. In fact, all $K_ S$-smooth arrays must contain a repeating pattern of length $K$. The image to the right shows an array of smoothies, and is totally unrelated to this problem, but may help you relax.

Any array can be made $K_ S$-smooth by changing its elements. In each change one element may be modified to any integer between $0$ and $S$, inclusive. You want to make all of your arrays smooth, but you don’t want to make any more changes than necessary. So the question is: What is the minimum number of changes you have to make so that a given array would become $K_ S$-smooth?

Input

The first line of input will consist of three integers of the form:

\[ N\; \; K\; \; S \]

where $N$ is the size of the array, The remainder of the file will consist of $N$ integers, $a_ n\in A$, separated by white space. All input will be within the following constraints:

\[ 1 \le K \le N \le 5000 \]\[ \forall a_ n \in A,\; 0 \le a_ n \le S \le 5000 \]

Output

Your program must output a single integer specifying the minimum number of changes that must be made in order to make the array $K_ S$ smooth.

Sample Input 1 Sample Output 1
3 3 5
1
2
3
1
Sample Input 2 Sample Output 2
6 3 5
1
2
3
3
2
1
3
Sample Input 3 Sample Output 3
5 1 5
1
2
3
4
5
4

Please log in to submit a solution to this problem

Log in