Smooth Array

Time limit2sMemory limit512 MB

Summary

Change the fewest array elements so every window of K consecutive values sums to exactly S, with values kept in [0, S].

Level: Medium7 of 10
Topics: Dynamic programming, Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

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 KS-smooth if the sum of every set of $K$ consecutive integers is exactly $S$ . Unfortunately, not all arrays are KS-smooth. In fact, every KS-smooth array 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 KS-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 KS-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 (spaces or newlines).

Output

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

Constraints

$1 \le K \le N \le 5000$
$\forall a_n \in A, 0 \le a_n \le S \le 5000$

Examples3

Example 1
Input
```
3 3 5
1
2
3
```
Expected output
```
1
```
Example 2
Input
```
6 3 5
1
2
3
3
2
1
```
Expected output
```
3
```
Example 3
Input
```
5 1 5
1
2
3
4
5
```
Expected output
```
4
```