Statement

Doragon the aqua dragon girl is playing in a linear cave. Initially, she is located at position 0 with N candies in his possession, and the exit is at position E. There are also N bears in the game. The i-th bear is located at $x_i$. The maximum moving speed of Doragon is 1 while the bears do not move at all.

When Doragon gives a candy to a bear, it will provide a coin after T units of time. More specifically, if the i-th bear is given a candy at time t, it will put a coin at its position at time t+T. The purpose of this game is to give candies to all the bears, pick up all the coins, and go to the exit. Note that Doragon can only give a candy to a bear if she is at the exact same position of the bear. Also, each bear will only produce a coin once. If Doragon visits the position of a coin after or at the exact same time that the coin is put down, she can pick up the coin. Coins do not disappear until collected by her.

You are given the configuration of the game. Please calculate the minimum time Doragon needs to collect all the coins and go to the exit.

Input

The first line contains N,E,T

The second line contains N integers, X1 to XN

Output

An integer

Example

Sample Input 1
3 9 1
1 3 8
Sample Output 1
12
The optimal strategy is to wait for the coin after treating each bear. The total time spent on waiting is 3 and moving is 9. So the answer is 3+9=12.

Sample Input 2
3 9 3
1 3 8
Sample Output 2
16

Sample Input 3
2 1000000000 1000000000
1 999999999
Sample Output 3
2999999996

Subtask

• For 95%, $N\leq 2000$

• For the other 5%, $1\leq N\leq 10^5$ If you want to get this 5%, you need to pass all testcases

• $1\leq T,E\leq 10^9,0\lt x_i\lt E$

• x is strictly increasing