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.

-----Examples-----
Sample Input 1:
3 3 5
1
2
3
Sample Output 1:
1

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

Difficulty: competition

Starter code:

Solutions: