Minimizing Total Waiting Time for Ferry Transportation

There are \(n\) students waiting to be ferried from Renmin High School to Renmin University. The \(i\)-th student arrives at time \(t_i\) minutes to wait for the ferry. Only one ferry is in operation, and it has an infinite capacity. The ferry departs from the high school, drops off all its passengers at the university, and then returns to the high school. A complete round trip always takes \(m\) minutes (boarding and alighting of the students are instantaneous). The ferry can depart immediately once it returns.

Your task is to schedule the departure times of the ferry so that every student is delivered to the university and the total waiting time is minimized. The waiting time for a student is defined as the difference between the departure time of the ferry that picks them up and their arrival time.

More formally, suppose you decide to run the ferry for \(k\) trips with departure times \(d_1, d_2, \dots, d_k\) satisfying \(d_j \ge d_{j-1} + m\) for \(j \ge 2\) (taking \(d_0 = 0\)). Every student must be assigned to one of these departures, and if a student with arrival time \(t_i\) is assigned to departure \(d_j\) (with \(d_j \ge t_i\)), their waiting time is \(d_j - t_i\). The goal is to minimize the sum of all students' waiting times.

Note: In an optimal solution, the ferry can carry all students that are waiting at the time of departure, and it is always optimal to serve the students in order of their arrival times.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n \le 2000, 1 \le m \le 10^9)\), representing the number of students and the duration of one complete round trip, respectively.

The second line contains \(n\) integers \(t_1, t_2, \dots, t_n\) \((0 \le t_i \le 10^9)\) representing the time each student arrives at the ferry stop. The arrival times are not necessarily in sorted order.

outputFormat

Output a single integer: the minimum total waiting time of all students.

sample

3 5
1 2 8

9