Trước bức tường cao của một phòng thí nghiệm bí mật, có ~N~ cảm biến có khả năng nhận diện những kẻ xâm nhập. Bức tường được biểu diễn bằng một đoạn thẳng ~[0, L]~, và các cảm biến ban đầu được đặt tại một số điểm nằm trên đoạn này.

Mỗi cảm biến có phạm vi nhận diện ~r~, và phạm vi này giống nhau với tất cả các cảm biến. Nói cách khác, một cảm biến tại vị trí ~p~ có thể nhận diện kẻ xâm nhập trong khoảng ~[p-r, p+r]~. Khoảng này được gọi là phạm vi nhận diện của cảm biến.

Một robot duy nhất có nhiệm vụ quản lý biên giới của bức tường. Ban đầu, robot được đặt tại đầu bên trái của bức tường (nghĩa là điểm ~0~) và không mang theo cảm biến nào. Robot có thể di chuyển sang trái hoặc phải dọc theo tường, đồng thời tháo lắp và cầm theo cảm biến. Robot chỉ có thể tháo hoặc lắp cảm biến tại vị trí bất kỳ trong đoạn ~[0, L]~. Số lượng cảm biến mà robot có thể mang theo cùng lúc là không giới hạn.

Nếu hợp của tất cả các phạm vi nhận diện của cảm biến bao phủ hoàn toàn đoạn tường ~[0, L]~, các cảm biến sẽ tạo ra một hàng rào bảo vệ hoàn hảo. Robot phải dời vị trí của các cảm biến nếu cần thiết để đạt được hàng rào bảo vệ hoàn hảo, đồng thời tối thiểu hóa tổng quãng đường di chuyển của robot.

Yêu cầu: Hãy viết chương trình tính tổng quãng đường di chuyển tối thiểu mà robot phải thực hiện để tạo ra hàng rào bảo vệ hoàn hảo, dựa trên độ dài đoạn tường ~[0, L]~, vị trí ban đầu của ~N~ cảm biến, và phạm vi nhận diện ~r~ của các cảm biến.

Input

Dòng đầu tiên chứa ba số nguyên ~N, L~, và ~r~, lần lượt biểu diễn số lượng cảm biến, chiều dài của bức tường, và phạm vi nhận diện của cảm biến.

Dòng thứ hai chứa ~N~ số nguyên, biểu diễn vị trí ban đầu của các cảm biến, được cho theo thứ tự không giảm.

Output

Nếu không thể đạt được hàng rào bảo vệ hoàn hảo, in ra -1 trên dòng đầu tiên.

Nếu có thể đạt được hàng rào bảo vệ hoàn hảo, in ra tổng quãng đường di chuyển tối thiểu mà robot phải thực hiện để đạt được. Giá trị này luôn là một số nguyên.

Scoring

• ~1 \le N \le 1000000~

• ~1 \le L \le 10^{12}~

• ~1 \le r \le 10^{12}~

• Cả ~L~ và ~r~ đều là số nguyên.

• Tất cả các vị trí ban đầu của cảm biến là số nguyên nằm trong khoảng ~[0, L]~.

• Vị trí ban đầu của các cảm biến được cho theo thứ tự không giảm.

Subtask	Điểm	Ràng buộc
1	~10\%~	~N \le 10, L \le 100, r \le 10~
2	~10\%~	~N \le 30, L \le 2000, r \le 30~
3	~15\%~	~N \le 500~
4	~30\%~	~N \le 2500~
5	~35\%~	Không có giới hạn gì thêm

Sample Input 1

5 20 2
4 10 11 17 19

Sample Output 1

36

Sample Input 2

5 18 2
7 10 12 14 18

Sample Output 2

22

Sample Input 3

4 18 3
8 10 14 18

Sample Output 3

17

Sample Input 4

1 33 4
33

Sample Output 4

-1