Description

The train stations in Upper Bytown and Lower Bytown are connected with a single-track rail link.

It takes the train $s$ minutes to travel between them in either direction.

However, the trains departing a station have to be spaced at least one minute apart.

Moreover, at all times, all the trains on the rail link have to go in the same direction.

According to the timetable at our disposal, $n$ cargo trains destined for Lower Bytown are to pass through Upper Bytown. They are to be loaded with goods in Lower Bytown and then return to Upper Bytown. For simplicity, we assume that loading the goods on the train takes virtually no time.

We are to determine the minimum possible time of the last train returning to Upper Bytown.

In summary: there are two towns. It takes $s$ minutes to go from A to B. There are $n$ trains that need to go from A to B and then come back. At any moment, only trains moving in the same direction may be on the track. Each train has an earliest departure time from A. Find the earliest time by which all trains have returned to station A.

Input Format

The first line of the standard input contains two integers $n$, $s$ ($1\le n\le 1\ 000\ 000$, $1\le s\le 10^9$), separated by a single space, that specify the number of trains and the one-way travel time respectively.

The second line contains $n$ integers $t_1,t_2,\cdots,t_n$ ($0\le t_1\le t_2\le\cdots\le t_n\le 10^9$), separated by a single space, that specify the arrival times of successive trains at the Upper Bytown station.

Output Format

Print a single integer: the minimum possible time of the last train returning to Upper Bytown.

3 4
1 8 11

20

Hint

Translated by ChatGPT 5