Migrated from Lutece 1047 Alice's birthday

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a road whose length is $n$. Now Alice lives at one of the end, and Bob lives at the other end. Today is Alice's birthday, and Bob wants to have a romantic night with Alice so he decides to go to Alice's home by car.

There are $m$ service stations on the road. Each station provides any one of the two services described below:

1. decreases the time which Bob's car needs to move one unit length by $1$. But the time can't be less then $0$.
2. makes the car move one unit length immediately.

Note that only one service can be provided in every station. That is to say, Bob can choose only one service at every station.

Now Alice is wondering the least time Bob may need to arrive her home.

As is known to everyone of you, Bob loves Alice very much. Could you tell Bob the answer to help Bob leave a good impression on Alice.

Input

The first line contains three integers $n$, $m$ and $t$, indicating the length of the road, the number of service stations, the time that Bob's car needs to move one unit length initially.

The second line contains $m$ integers $p_i$, indicating the distance from Bob's home to the $i_{th}$ station.

It is guaranteed that $1 \leq n \leq 10^9, 0 \leq m \leq 10^5, 1 \leq t < 2^{31}, 1 \leq p_{i-1} < p_i < n$.

Output

Print the answer in one line.

Samples

10 2 7
1 6

55

Resources

The 13th UESTC Programming Contest Final