시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 1024 MB117131326.000%

문제

비요뜨는 오렌지 농장을 가지고 있다. 오렌지 농장은 현재 오렌지가 심겨 있지 않으며, 좌우로 직선형 구조를 가진다. 오렌지 농장의 맨 왼쪽 위치에는 입구가 있다.

오렌지 농장 위에는 오렌지를 심을 수 있는 지점이 $N$곳 있으며, 이들은 각각 입구에서 오른쪽으로 $x_1, x_2, \cdots, x_N$만큼 오른쪽으로 떨어진 위치에 있다.

비요뜨는 거리 1을 이동하는 데 1만큼의 시간이 걸린다. 또한 오렌지를 한 번 심으면 $K$의 시간 뒤에 오렌지 열매가 자라 먹을 수 있게 된다. 오렌지 열매를 심거나 다 자란 열매를 먹는 데에는 시간이 소요되지 않는다.

비요뜨는 오렌지 농장의 입구에서 출발해, $N$개의 지점에 오렌지를 하나씩 심고 $N$개의 오렌지를 모두 먹으려 한다. 비요뜨가 오렌지를 모두 먹는 데 걸리는 최소 시간을 계산하자.

입력

첫 줄에는 심을 오렌지의 수 $N$과 오렌지가 자라는 데 걸리는 시간 $K$가 주어진다.

둘째 줄에는 오렌지를 심을 수 있는 $N$개의 지점과 오렌지 농장의 입구와의 거리 $x_1, x_2, \cdots, x_N$이 오름차순으로 주어진다.

출력

비요뜨가 오렌지를 모두 먹는 데 걸리는 최소 시간을 출력한다.

제한

  • $1 \le N \le 3 \times 10^5$
  • $0 \le K \le 10^9$
  • $1 \le x_1 < x_2 < \cdots < x_N \le 10^9$

서브태스크

번호 배점 제한
1 9

$K = 0$

2 40

$N \le 1000$

3 51

추가 제한 조건이 없다.

예제 입력 1

5 0
1 3 5 7 9

예제 출력 1

9

예제 입력 2

5 4
1 2 3 11 12

예제 출력 2

20

출처

Contest > Orange Cup > Orange Cup I번

채점 및 기타 정보

  • 예제는 채점하지 않는다.