시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB169960.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 (spaces or newlines).

출력

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

출처

ICPC > Regionals > North America > North Central North America Regional > NCNA 2017 D번

  • 문제의 오타를 찾은 사람: jh05013
  • 문제를 만든 사람: Bowen Yu, Larry D. Pyeatt