Freight

Time limit1sMemory limit256 MB

Summary

Schedule n freight trains over a single track with travel time s and one-minute departure gaps so the last train returns to Upper Bytown as early as possible.

Level: Medium7 of 10
Topics: Greedy, Simulation
Solved: No attempts yet

Problem

The train stations of Upper Bytown and Lower Bytown are joined by a single track. A train needs $s$ minutes to travel between them, in either direction. Trains leaving the same station must depart at least one minute apart. At every moment, all trains on the track have to move in the same direction. A train may depart from a station at the exact minute another train arrives there.

According to the timetable, $n$ freight trains bound for Lower Bytown pass through Upper Bytown. Train $i$ reaches Upper Bytown at minute $t_i$ and cannot depart before that. Each train runs to Lower Bytown, takes on goods there, and returns to Upper Bytown. Loading the goods takes no time.

Find the earliest minute at which the last train can be back in Upper Bytown.

Input

The first line contains two integers $n$ and $s$ separated by a single space, the number of trains and the one-way travel time ( $1 \le n \le 10^6$ , $1 \le s \le 10^9$ ). The second line contains $n$ integers $t_1, t_2, \dots, t_n$ separated by single spaces, the arrival times of the trains at the Upper Bytown station ( $0 \le t_1 \le t_2 \le \dots \le t_n \le 10^9$ ).

Output

Print one line with a single integer: the earliest minute at which the last train is back in Upper Bytown.

Hint

In the first example the minimum is reached when the trains leave Upper Bytown at minutes 1, 9 and 11, and leave Lower Bytown at minutes 5, 15 and 16.

Examples2

Example 1
Input
```
3 4
1 8 11
```
Expected output
```
20
```
Example 2
Input
```
1 1
0
```
Expected output
```
2
```