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

#5500

보는 곰 1s 32MB

문제

곰은 WBB라는 프로그램을 즐겨 본다. 곰은 바쁘기에 다음 N일 동안 WBB를 보기 위한 계획을 세웠다.

WBB는 구독제로 운영하고 있기에 곰은 최소 금액을 지불할 계획을 세워야 한다.

WBB는 특별한 구독 시스템을 운영하고 있다. 연속된 d일 동안 구독한다면 d+K원을 지불해야 한다.

구독 시작은 아무 때나 가능하며 현재 구독이 끝나면 원하는 만큼 새롭게 구독을 시작할 수 있다.

이를 고려하여 곰이 지불할 최소 금액을 구해야 한다.


입력

첫 줄에 N과 K가 주어진다. (1 \leq N \leq 10^5, 1\le K\le 10^9)

두 번째 줄에 N개의 수가 주어진다. 각 수는 곰이 WBB를 보는 날짜이다. (1≤d_1<d_2<⋯<d_N≤10^{14}).


출력

곰이 지불할 최소 금액을 출력한다.

이 문제와 관련된 큰 크기의 정수에는 64비트 정수 데이터 유형(예: C/C++의 "long long")을 사용해야 할 수도 있습니다.


예제 #1

2 4

7 9
7

7일차에 3일간 구독하여 d+K=3+4=7원을 지불하면 된다.


예제 #2

2 3

1 10
8

(예제2)

1일차에 1일간 구독하여 d+K=1+3=4원을 지불한다. 또한 10일차에 1일간 구독하여 d+K=1+3=4원을 지불한다. 따라서 총 8원을 지불하면 된다.



출처

USACO 2023 February Bronze

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