Evacuation Optimization

In order to avoid the disaster caused by a solar explosion, humanity has decided to install engines on Earth to eventually escape from the solar system. However, the plan to take the Moon along has failed due to a catastrophic malfunction of the Moon engine. As a result, the personnel stationed on the Moon must be evacuated back to Earth.

The Moon base has one space shuttle available for evacuation. The personnel are scattered around and arrive at the base at different times. The shuttle, which is assumed to be large enough to carry all waiting personnel, can be scheduled to depart at any desired time. In each trip, the shuttle departs from the Moon base, takes the currently waiting personnel to Earth, and then returns to the base. Each round‐trip takes exactly \(M\) hours.

There are \(N\) personnel in total. The arrival time of the \(i\)th person is \(T_i\) (in hours). When a group of people boards a trip, if the shuttle departs at time \(d\), then the waiting time for a person with arrival time \(T_i\) in that trip is \(d - T_i\) (assume \(d\ge T_i\)). For a chosen group, the optimal departure time is the smallest possible time that is no less than both the time the shuttle becomes available and the latest arrival in that group. In other words, if the shuttle becomes available at time \(v\) and the group (after sorting by arrival times) has last arrival \(T_j\), then the departure time is \(d = \max(v, T_j)\) and the waiting time for that group is \[ \sum_{i\in\text{group}} (d - T_i) = (\text{size of group})\cdot d - \sum_{i\in\text{group}} T_i. \]

The shuttle can be scheduled arbitrarily (its departure times chosen freely, subject to the constraint that it cannot depart until it returns from the previous trip). The goal is to plan the evacuation trips so that the total waiting time of all personnel is minimized.

Example:

Suppose \(N=5\), \(M=4\), and the arrival times are 11, 3, 3, 5, 10 respectively. One optimal plan is as follows:

• The shuttle departs at time 3 (\(d=3\)) to evacuate the personnel who arrived at time 3 (two personnel). Their waiting time is \(3-3=0\) for each.
• The shuttle returns at time \(3+4=7\). At this point, the person who arrived at time 5 has been waiting for \(7-5=2\) hours. Immediately, the shuttle departs at time 7 and evacuates this person.
• The shuttle returns at time \(7+4=11\). By then, the remaining two personnel have arrived at times 10 and 11. Their waiting times are \(11-10=1\) and \(11-11=0\) respectively. The shuttle departs at 11, evacuating both.

The total waiting time is \(2+1=3\) hours, which is optimal.

Input constraints and notes: The input begins with two integers \(N\) and \(M\), followed by a line with \(N\) integers representing the arrival times \(T_i\). You may assume that the numbers are such that an optimal solution exists under the above strategy.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of personnel and the shuttle round-trip time, respectively). The second line contains \(N\) integers: \(T_1, T_2, ..., T_N\), where \(T_i\) is the time at which the \(i\)th person arrives at the base.

outputFormat

Output a single integer representing the minimal total waiting time (in hours) over all personnel.

sample

5 4
11 3 3 5 10

3