Problem D
Smooth Array
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 |
