Problem Background

NOIP2018 Junior Group T3

Problem Description

There are $n$ students who need to take a shuttle bus from Renmin University Affiliated High School to Renmin University. The $i$-th student arrives at the bus stop at the $t_i$-th minute. There is only one shuttle bus in operation, but its capacity is virtually unlimited. The shuttle bus travels from Renmin University Affiliated High School to Renmin University, drops off the students, and returns to Renmin University Affiliated High School (to pick up more students), taking a total of $m$ minutes for a round trip (ignoring the time for students to get on and off the bus). The shuttle bus must transport all students to Renmin University.

Kaikai is curious about the minimum total waiting time for all students if he can arrange the departure time of the shuttle bus arbitrarily.

Note: The shuttle bus can depart immediately upon returning to Renmin University Affiliated High School.

Input Format

The first line contains two positive integers $n$ and $m$, separated by a space, representing the number of students waiting and the time it takes for the shuttle bus to complete a round trip, respectively.
The second line contains $n$ positive integers, separated by spaces, where the $i$-th non-negative integer $t_i$ represents the time at which the $i$-th student arrives at the bus stop.

Output Format

Output a single integer, representing the minimum total waiting time for all students (in minutes).

Sample Input and Output

Sample Input #1

5 1
3 4 4 3 5

Sample Output #1

0

Sample Input #2

5 5
11 13 1 5 5

Sample Output #2

4

Notes

Sample 1 Explanation

Students 1 and 4 start waiting at the 3rd minute, wait for 0 minutes, and board the shuttle bus at the 3rd minute. The shuttle bus returns to Renmin University Affiliated High School at the 4th minute.
Students 2 and 3 start waiting at the 4th minute, wait for 0 minutes, and board the shuttle bus at the 4th minute. The shuttle bus returns to Renmin University Affiliated High School at the 5th minute.
Student 5 starts waiting at the 5th minute, waits for 0 minutes, and boards the shuttle bus at the 5th minute. All students are now transported to Renmin University. The total waiting time is 0.

Sample 2 Explanation

Student 3 starts waiting at the 1st minute, waits for 0 minutes, and boards the shuttle bus at the 1st minute. The shuttle bus returns to Renmin University Affiliated High School at the 6th minute.
Students 4 and 5 start waiting at the 5th minute, wait for 1 minute, and board the shuttle bus at the 6th minute. The shuttle bus returns to Renmin University Affiliated High School at the 11th minute.
Student 1 starts waiting at the 11th minute, waits for 2 minutes; Student 2 starts waiting at the 13th minute, waits for 0 minutes. They board the shuttle bus at the 13th minute. All students are now transported to Renmin University. The total waiting time is 4.
It can be proven that there is no plan with a total waiting time less than 4.

Data Range and Constraints

For 10% of the data, $n ≤ 10$, $m = 1$, $0 ≤ t_i ≤ 100$.
For 30% of the data, $n ≤ 20$, $m ≤ 2$, $0 ≤ t_i ≤ 100$.
For 50% of the data, $n ≤ 500$, $m ≤ 100$, $0 ≤ t_i ≤ 10^4$.
For another 20% of the data, $n ≤ 500$, $m ≤ 10$, $0 ≤ t_i ≤ 4 \times 10^6$.
For 100% of the data, $n ≤ 500$, $m ≤ 100$, $0 ≤ t_i ≤ 4 \times 10^6$.

见题面 Input 部分

见题面 Output 部分