Mooloo 시청하기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

시청 날짜 N개가 주어질 때, 길이가 d인 구독의 비용이 d+K이고 모든 시청 날짜를 덮어야 할 때의 최소 비용을 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 구간, 그리디
정답자: 아직 제출이 없습니다

문제

Bessie는 Mooloo에서 방송 보기를 좋아한다. Bessie는 바쁜 소라서 앞으로 $N$ 일( $1 \leq N \leq 10^5$ ) 동안 Mooloo를 볼 일정을 세웠다. Mooloo는 유료 구독 서비스이므로 Bessie는 지불할 금액을 최소로 하는 방법을 정해야 한다.

Mooloo에는 독특한 구독 제도가 있다. $d$ 일 동안 구독하는 데 $d + K$ ( $1 \le K \le 10^9$ ) moonies가 든다. 구독은 언제든지 시작할 수 있고, 현재 구독이 만료되면 원하는 만큼 횟수 제한 없이 새로 시작할 수 있다. Bessie가 일정을 소화하는 데 필요한 최소 금액을 구하라.

입력

첫째 줄에 정수 $N$ 과 $K$ 가 주어진다.

둘째 줄에는 Bessie가 Mooloo를 볼 날을 나타내는 $N$ 개의 정수가 주어진다: $1\le d_1<d_2<\dots<d_N\le 10^{14}$ .

출력

이 문제에 나오는 정수는 매우 클 수 있으므로 64비트 정수 자료형(C/C++에서는 "long long" 등)을 사용해야 할 수도 있다.

예제2

예제 1
입력
```
2 4
7 9
```
예상 출력
```
7
```
예제 2
입력
```
2 3
1 10
```
예상 출력
```
8
```