시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 5 2 2 40.000%

문제

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, all KS-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 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?

입력

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, an ∈ A, separated by white space. All input will be within the following constraints:

출력

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.

제한

  • 1 ≤ K ≤ N ≤ 5000
  • ∀an ∈ A, 0 ≤ an ≤ S ≤ 5000

예제 입력 1

3 3 5
1
2
3

예제 출력 1

1

예제 입력 2

6 3 5
1
2
3
3
2
1

예제 출력 2

3

예제 입력 3

5 1 5
1
2
3
4
5

예제 출력 3

4