頁面無法載入？點擊這裡可能會修復。
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

需要登入才能撰寫程式碼。