32032번 - 만보기 대행 서비스

문제

요즘 세상에는 일상생활 속 미션을 수행하면서 포인트를 얻고 소정의 상품도 얻어갈 수 있는 앱테크 서비스가 많다. 만보기 미션은 여러 앱테크 서비스에서 널리 사용하고 있는데, 매일 Dm 걷기에 성공하면 약간의 포인트를 얻을 수 있다.

매일 Dm씩 걷는 게 생각보다 번거로운 일이기 때문에, 미션을 직접 수행하기 귀찮아하는 사람들을 위해 한별이는 만보기 미션을 대행해주는 사업을 하는 스타트업 스타트한별을 창업하였다. 스타트한별에서는 우선 스타트한별 사옥을 지나는 동서쪽으로 길게 이어진 도로 위에 1m 간격으로 보관함을 설치하고 정수 번호를 매겼다. 스타트한별 사옥에서 동쪽으로 Am 떨어진 보관함의 번호는 A, 서쪽으로 Am 떨어진 보관함의 번호는 −A, 사옥에 있는 보관함의 번호는 0이다.

당신은 스타트한별 사옥에서 출발하여 모든 고객의 미션을 수행한 다음 회사로 복귀해야 한다. 당신이 업무를 시작하기 전에 이미 모든 고객이 X_i번 보관함에 휴대폰을 놓아두었다. 당신은 X_i번 보관함까지 가서 휴대폰을 직접 집어야 하고, 집은 이후 Dm 이상 움직인 다음 X_i번 보관함에 휴대폰을 반납해야 한다. 당신은 충분히 큰 가방을 갖고 업무를 수행하기 때문에 여러 휴대폰을 동시에 넣어서 움직일 수 있다. 당신의 이동기록은 근무 기록으로 반영되기 때문에 반드시 도로 위에서만 움직여야 한다.

모든 고객의 미션을 수행하고 복귀하기 위해 움직여야 할 최소 거리를 구하는 프로그램을 작성하여라.

입력

첫 줄에 고객의 수 N과 미션을 수행하기 위해 걸어야 할 최소 이동 거리 D가 공백을 사이에 두고 주어진다. (1 ≤ N ≤ 1 000 000; 1 ≤ D ≤ 10⁹)

둘째 줄에 각 고객이 휴대폰을 놓은 보관함의 번호를 나타내는 N개의 정수 X_i가 공백을 사이에 두고 주어진다. (−10⁹ ≤ X_i ≤ 10⁹)

휴대폰의 위치가 서로 겹치거나 스타트한별 사옥과 같은 곳에 있을 수 있다.

모든 입력 값은 정수이다.

출력

첫 줄에 고객 N명의 미션을 모두 수행하고 복귀하기 위해 필요한 최소 이동 거리를 출력한다.

정답이 정수가 아닌 경우, 정답보다 작거나 같은 가장 큰 정수를 출력한다.

제한

노트

아래 방법을 사용하는 게 최적이다.

1. 2번째 고객의 휴대폰을 집는다.
2. 3번째 고객의 휴대폰을 집는다.
3. 스타트한별 사옥 동쪽 7.5m 지점까지 이동한 후 돌아와서 3번째 고객의 휴대폰을 반납한다.
4. 2번째 고객의 휴대폰을 반납한다.
5. 1번째 고객의 휴대폰을 집는다.
6. 스타트한별 사옥 서쪽 10.5m 지점까지 이동한 후 돌아와서 1번째 고객의 휴대폰을 반납한다.
7. 스타트한별 사옥으로 이동한다.