Single Track Train Scheduling

There are two towns, A and B. It takes (s) minutes to travel from A to B. There are (n) cargo trains that must depart from A, travel to B, and then return to A. Each train has an earliest departure time from A. The following constraints must be observed:

1. The travel time between A and B is (s) minutes in either direction.
2. Trains departing from a station must be spaced at least one minute apart.
3. At any given time, all trains on the rail link must be travelling in the same direction.
4. Loading/unloading time at B is negligible.

Your task is to schedule the departures such that the last train returns to A as early as possible. The optimal strategy is to schedule the trains from A to B in increasing order of their earliest departure times. If the sorted earliest departure times are (a_1, a_2, \dots, a_n), then the actual departure time (d_i) for the (i^{th}) train (using 0-indexing) is given by:

[ d_0 = a_1, \quad d_i = \max(a_{i+1}, d_{i-1}+1) \quad \text{for } i \ge 1. ]

After the last train departs from A at time (d_{n-1}), its arrival time at B is (d_{n-1} + s). Because all trains must complete the A (\to) B phase before any return (to avoid having trains on the track in opposite directions), the return trips from B to A must start after the last A (\to) B train arrives at B. The return departures from B can then be scheduled in a similar one-minute spaced fashion. Specifically, if the first return departure is at time (d_{n-1} + s), then the return departure for the (i^{th}) train is (r_i = d_{n-1} + s + i), and its arrival time back to A is (r_i + s). The time when all trains have returned is therefore:

[ d_{n-1} + 2s + (n-1). ]

Compute this minimal final time given the scheduling constraints.

inputFormat

The first line contains two space-separated integers \(n\) and \(s\): the number of trains and the travel time between the two towns.

The second line contains \(n\) space-separated integers, where the \(i^{th}\) integer represents the earliest departure time of the \(i^{th}\) train from A.

outputFormat

Output a single integer representing the minimal time at which all trains return to A.

sample

3 2
1 1 3

9