매끄러운 배열

시간 제한2초메모리 제한512 MB

요약

배열의 원소를 최소한으로 바꿔서 길이 K인 모든 연속 구간의 합이 정확히 S가 되도록 만들고, 그 최소 변경 횟수를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 수학, 조합론, 구현
정답자: 아직 제출이 없습니다

문제

살다 보면 모든 일이 매끄럽게 흘러가길 바라게 되고, 매끄러운 배열이 있으면 도움이 될지도 모른다. 음이 아닌 정수 N개로 이루어진 배열 A가 KS-매끄럽다(KS-smooth)는 것은 연속한 K개의 정수의 합이 항상 정확히 S인 것이다. 안타깝게도 모든 배열이 KS-매끄러운 것은 아니다. 실제로 KS-매끄러운 배열은 반드시 길이 K의 반복 패턴을 가진다. 오른쪽 그림은 스무디 배열을 보여 주는데, 이 문제와는 전혀 관계가 없지만 마음을 편안하게 하는 데는 도움이 될 것이다.

모든 배열은 원소를 바꿔서 KS-매끄럽게 만들 수 있다. 한 번의 변경에서는 한 원소를 0 이상 S 이하의 임의의 정수로 바꿀 수 있다. 모든 배열을 매끄럽게 만들고 싶지만, 필요한 것보다 더 많이 바꾸고 싶지는 않다. 따라서 질문은 이것이다. 주어진 배열이 KS-매끄러워지도록 하려면 최소 몇 번을 바꿔야 하는가?

입력

입력의 첫 줄은 다음 형식의 정수 세 개로 이루어진다.

N K S

여기서 N은 배열의 크기이다. 파일의 나머지 부분은 공백(스페이스 또는 줄바꿈)으로 구분된 N개의 정수, an ∈ A로 이루어진다.

출력

배열을 KS-매끄럽게 만들기 위해 필요한 최소 변경 횟수를 나타내는 정수 하나를 출력한다.

제한

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

예제3

예제 1
입력
```
3 3 5
1
2
3
```
예상 출력
```
1
```
예제 2
입력
```
6 3 5
1
2
3
3
2
1
```
예상 출력
```
3
```
예제 3
입력
```
5 1 5
1
2
3
4
5
```
예상 출력
```
4
```