페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8477
서브태스크

소들의 키 3s 1024MB

문제

농부 John 은 N 마리의 소들을 키우고 있다.

i 번째 소의 키는 H_i 이다. (~i~= ~1,~ 2,~ ...~ , ~ N ~)

John 의 목표는 모든 인접한 소의 키 차이가 K 이하가 되게 만드는 것이다.

즉, 모든 1 ≤ i < N 에 대해 |H_{i+1}-H_i|≤K 가 되는 것이다.

John 은 1원의 비용을 들여, 소 하나를 골라 키를 원하는 정수로 바꿀 수 있다.

목표를 달성하기 위한 최소 비용을 구하자.


입력

첫 줄에 두 정수 N 과 K 가 입력된다. ( 1 ≤ N ≤ 50만, 0 ≤K≤ 1012 )

두 번째 줄에 각 소들의 키 H_i 가 입력된다. ( 각각 1012 이하의 자연수 )


출력

목표를 달성하기 위한 최소 비용을 출력한다.


부분문제

번호 점수 조건
#110점

K=0

#220점

1 ≤ N ≤ 20

#350점

1 ≤ N ≤ 1,000

#420점

제약 조건 없음


예제 #1

5 3
1 4 7 7 10000
1

마지막 소의 키만 4~10 범위의 수로 바꾸면 된다.


예제 #2

12 2
1 8 3 5 19 23 38 21 18 4 5 1
7


출처

KCPC 2024 예비소집 C번

로그인해야 코드를 작성할 수 있어요.