만보기 대행 서비스

요즘에는 일상생활 속 미션을 수행하고 포인트와 소정의 상품을 받을 수 있는 앱테크 서비스가 많다. 만보기 미션은 여러 앱테크 서비스에서 널리 쓰이며, 매일 $D$m 걷기에 성공하면 약간의 포인트를 받을 수 있다.

매일 $D$m씩 걷는 일은 생각보다 번거롭다. 그래서 미션을 직접 수행하기 귀찮아하는 사람들을 위해 한별이는 만보기 미션을 대행하는 스타트업 스타트한별을 창업했다. 스타트한별은 사옥을 지나는 동서 방향 도로 위에 1m 간격으로 보관함을 설치하고 정수 번호를 매겼다. 사옥에서 동쪽으로 $A$m 떨어진 보관함의 번호는 $A$, 서쪽으로 $A$m 떨어진 보관함의 번호는 $-A$, 사옥에 있는 보관함의 번호는 0이다.

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

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

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

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

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

모든 입력 값은 정수이다.

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

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

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

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