Background

NOIP 2018 Junior Group T3.

Problem Description

There are $n$ students who need to take a ferry shuttle from RDFZ (Renmin University Affiliated High School) to Renmin University. The $i$-th student goes to wait for the shuttle at minute $t_i$. Only one shuttle is in service, but its capacity can be considered unlimited. The shuttle departs from RDFZ, takes the students on board to Renmin University, and then returns to RDFZ (to pick up other students). One round trip takes a total of $m$ minutes (ignore the time for getting on and off). The shuttle must deliver all students to Renmin University.

Kaikai is curious: if he can arrange the shuttle’s departure times arbitrarily, what is the minimum possible sum of all students’ waiting times?

Note: after the shuttle returns to RDFZ, it can depart again immediately.

Input Format

The first line contains two positive integers $n, m$, separated by a space, representing the number of waiting students and the time for one round trip of the shuttle.

The second line contains $n$ positive integers, separated by spaces. The $i$-th non-negative integer $t_i$ represents the time when the $i$-th student arrives at the station.

Output Format

Output one line with one integer, representing the minimum possible sum of all students’ waiting times (in minutes).

5 1 
3 4 4 3 5 

0

5 5 
11 13 1 5 5 

4

Hint

Explanation of Sample 1

Students $1$ and $4$ start waiting at minute $3$, wait $0$ minutes, and depart on the shuttle at minute $3$. The shuttle returns to RDFZ at minute $4$.

Students $2$ and $3$ start waiting at minute $4$, wait $0$ minutes, and depart on the shuttle at minute $4$. The shuttle returns to RDFZ at minute $5$.

Student $5$ starts waiting at minute $5$, waits $0$ minutes, and departs on the shuttle at minute $5$. From then on, all students have been delivered to Renmin University. The total waiting time is $0$.

Explanation of Sample 2

Student $3$ starts waiting at minute $1$, waits $0$ minutes, and departs on the shuttle at minute $1$. The shuttle returns to RDFZ at minute $6$.

Students $4$ and $5$ start waiting at minute $5$, wait $1$ minute, and depart on the shuttle at minute $6$. The shuttle returns to RDFZ at minute $11$.

Student $1$ starts waiting at minute $11$ and waits $2$ minutes; student $2$ starts waiting at minute $13$ and waits $0$ minutes. They depart on the shuttle at minute $13$. From then on, all students have been delivered to Renmin University. The total waiting time is $4$.

It can be proven that there is no plan with total waiting time less than $4$.

Constraints

For $10\%$ of the testdata, $n \le 10$, $m = 1$, $0 \le t_i \le 100$.

For $30\%$ of the testdata, $n \le 20$, $m \le 2$, $0 \le t_i \le 100$.

For $50\%$ of the testdata, $n \le 500$, $m \le 100$, $0 \le t_i \le 10^4$.

For another $20\%$ of the testdata, $n \le 500$, $m \le 10$, $0 \le t_i \le 4 \times 10^6$.

For $100\%$ of the testdata, $n \le 500$, $m \le 100$, $0 \le t_i \le 4 \times 10^6$.

Translated by ChatGPT 5