Robotai

Interview

Time limit1sMemory limit1024 MB

Summary

Two robots start at both ends of a furrow of length L and plant M trees at given positions. Find the minimum time to plant all of them.

Level: Medium5 of 10
Topics: Binary search, Greedy
Solved: No attempts yet

Problem

A straight furrow of length $L$ must have $M$ trees planted in it. Robots plant the trees, so every distance in the furrow is measured in robopėdos (robot feet).

The positions (distances from the start of the furrow) are $P_1, P_2, \dots, P_M$ . A single tree must be planted at each of these positions.

Two robots do the work. Each robot moves 1 robot foot per 1 time unit, and it takes $S$ time units to plant one tree. The first robot starts at position $0$ , and the second robot starts at position $L$ . Both robots start working at time $0$ .

Write a program that finds the minimum time $T$ needed to plant all the trees when both robots work.

Input

The first line contains three integers $M$ , $L$ , and $S$ . $M$ is the number of positions, $L$ is the length of the furrow, and $S$ is the time needed to plant one tree.

Each of the next $M$ lines contains one integer, the planting positions $P_1, P_2, \dots, P_M$ , given in increasing order.

Output

Print one line with the minimum time $T$ .

Constraints

$1 \le M \le 10^6$

$1 \le L \le 10^9$

$1 \le S \le 10^3$

$0 \le P_i \le L$

Examples3

Example 1
Input
```
3 8 1
1
3
6
```
Expected output
```
5
```
Example 2
Input
```
5 5 2
1
2
3
4
5
```
Expected output
```
8
```
Example 3
Input
```
3 17 3
0
2
4
```
Expected output
```
13
```