요즘 세상에는 일상생활 속 미션을 수행하면서 포인트를 얻고 소정의 상품도 얻어갈 수 있는 앱테크 서비스가 많다. 만보기 미션은 여러 앱테크 서비스에서 널리 사용하고 있는데, 매일 $D$m 걷기에 성공하면 약간의 포인트를 얻을 수 있다.
매일 $D$m씩 걷는 게 생각보다 번거로운 일이기 때문에, 미션을 직접 수행하기 귀찮아하는 사람들을 위해 한별이는 만보기 미션을 대행해주는 사업을 하는 스타트업 스타트한별을 창업하였다. 스타트한별에서는 우선 스타트한별 사옥을 지나는 동서쪽으로 길게 이어진 도로 위에 $1$m 간격으로 보관함을 설치하고 정수 번호를 매겼다. 스타트한별 사옥에서 동쪽으로 $A$m 떨어진 보관함의 번호는 $A$, 서쪽으로 $A$m 떨어진 보관함의 번호는 $-A$, 사옥에 있는 보관함의 번호는 $0$이다.
당신은 스타트한별 사옥에서 출발하여 모든 고객의 미션을 수행한 다음 회사로 복귀해야 한다. 당신이 업무를 시작하기 전에 이미 모든 고객이 $X_i$번 보관함에 휴대폰을 놓아두었다. 당신은 $X_i$번 보관함까지 가서 휴대폰을 직접 집어야 하고, 집은 이후 $D$m 이상 움직인 다음 $X_i$번 보관함에 휴대폰을 반납해야 한다. 당신은 충분히 큰 가방을 갖고 업무를 수행하기 때문에 여러 휴대폰을 동시에 넣어서 움직일 수 있다. 당신의 이동기록은 근무 기록으로 반영되기 때문에 반드시 도로 위에서만 움직여야 한다.
모든 고객의 미션을 수행하고 복귀하기 위해 움직여야 할 최소 거리를 구하는 프로그램을 작성하여라.
Input
첫 줄에 고객의 수 $N$과 미션을 수행하기 위해 걸어야 할 최소 이동 거리 $D$가 공백을 사이에 두고 주어진다. ($1 \leq N \leq 1\,000\,000$; $1 \leq D \leq 10^9$)
둘째 줄에 각 고객이 휴대폰을 놓은 보관함의 번호를 나타내는 $N$개의 정수 $X_i$가 공백을 사이에 두고 주어진다. ($-10^9 \leq X_i \leq 10^9$)
휴대폰의 위치가 서로 겹치거나 스타트한별 사옥과 같은 곳에 있을 수 있다.
모든 입력 값은 정수이다.
Output
첫 줄에 고객 $N$명의 미션을 모두 수행하고 복귀하기 위해 필요한 최소 이동 거리를 출력한다.
정답이 정수가 아닌 경우, 정답보다 작거나 같은 가장 큰 정수를 출력한다.
Examples
Input 1
3 5 -8 1 5
Output 1
36
Note
아래 방법을 사용하는 게 최적이다.
- $2$번째 고객의 휴대폰을 집는다.
- $3$번째 고객의 휴대폰을 집는다.
- 스타트한별 사옥 동쪽 $7.5$m 지점까지 이동한 후 돌아와서 $3$번째 고객의 휴대폰을 반납한다.
- $2$번째 고객의 휴대폰을 반납한다.
- $1$번째 고객의 휴대폰을 집는다.
- 스타트한별 사옥 서쪽 $10.5$m 지점까지 이동한 후 돌아와서 $1$번째 고객의 휴대폰을 반납한다.
- 스타트한별 사옥으로 이동한다.