경계 로봇

비밀 연구소의 높은 장벽 앞에는 침입자를 식별할 수 있는 N개의 센서가 놓여 있다. 장벽은 일직선으로 뻗어 있으며, 직선 위의 구간 $[0, L]$로 나타낸다. 센서는 이 구간 안에 놓인 점으로 나타낸다.

모든 센서는 같은 식별 범위 $r$을 가진다. 점 $p$에 있는 센서는 구간 $[p - r, p + r]$에 속한 침입자를 식별할 수 있다. 이 구간을 센서의 식별 구간이라고 한다.

장벽의 경계를 담당하는 로봇이 하나 있다. 로봇은 처음에 장벽의 왼쪽 끝에 있다. 로봇은 장벽을 따라 좌우로 움직이며 센서를 실어 옮길 수 있다. 로봇은 자기 위치에서만 센서를 싣거나 놓을 수 있다. 다만 한 번에 실을 수 있는 센서의 개수에는 제한이 없다.

모든 센서의 식별 구간의 합집합이 장벽 $[0, L]$을 완전히 포함하면, 센서가 완벽한 경계에 있다고 한다. 로봇은 완벽한 경계를 만들기 위해 필요하면 센서를 옮겨야 한다. 이때 로봇이 움직인 총 거리를 최소화해야 한다.

장벽 $[0, L]$, 센서 N개의 초기 위치, 식별 범위 $r$이 주어질 때, 완벽한 경계를 만들기 위해 로봇이 움직여야 하는 총 거리의 최솟값을 출력하는 프로그램을 작성하시오.

첫 줄에 센서의 개수 N, 장벽의 길이 L, 센서의 식별 범위 r이 공백으로 구분되어 주어진다.

둘째 줄에는 센서들의 초기 위치 N개가 공백으로 구분되어 주어진다. 위치는 단조 증가하는 순서로 주어지므로, 입력은 이미 정렬되어 있다.

센서를 어떻게 배치하더라도 완벽한 경계를 만들 수 없다면, 첫 줄에 -1을 출력한다.

완벽한 경계를 만들 수 있다면, 첫 줄에 로봇이 움직여야 하는 총 거리의 최솟값을 출력한다. 이 값은 항상 정수임을 증명할 수 있다.

• N은 1 이상 1,000,000 이하의 정수이다.
• L은 1 이상 $10^{12}$ 이하의 정수이다.
• r은 1 이상 $10^{12}$ 이하의 정수이다.
• L과 r은 모두 정수이다.
• 모든 센서의 초기 위치는 0 이상 L 이하의 정수이다.
• 모든 센서의 초기 위치는 단조 증가하는 순서로 주어진다.

첫 번째 예제의 경우, 다음과 같이 로봇이 움직이는 것이 최적이다.

1. 0에 있는 로봇이 3으로 이동한다.
2. 현재 위치에 있는 센서를 싣는다.
3. 3에 있는 로봇이 2로 이동한다.
4. 실은 센서를 현재 위치에 놓는다.

이때 센서의 최종 위치는 2와 6이고, 식별 구간의 합집합은 $[0, 8]$이다. 이는 장벽 $[0, 7]$을 완전히 포함한다. 로봇이 움직인 총 거리는 4이다. 이보다 적게 움직여서는 완벽한 경계를 만들 수 없으므로 답은 4이다.

두 번째 예제의 경우, 다음과 같이 로봇이 움직이는 것이 최적이다.

1. 위치 0에 있는 센서 두 개를 모두 싣는다.
2. 0에 있는 로봇이 1.5로 이동한다.
3. 실은 센서 중 하나를 현재 위치에 놓는다.
4. 1.5에 있는 로봇이 7로 이동한다.
5. 남은 센서 하나를 현재 위치에 놓는다.

로봇은 정수가 아닌 위치에도 센서를 놓을 수 있으니 유의하라.