该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

2018 T3 摆渡车

主知识点：动态规划。交叉标签：动态规划、前缀和。
暴力标注：DP 可用暴力拿部分分。
OJ 使用标准输入与标准输出。原比赛文件名为 bus.in / bus.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 2 秒；内存 256 MiB；测试点 20；总分 100。
数据来源：官网数据；与公开存档逐文件一致。

题目描述

有 $n$ 名乘客，第 $i$ 人在整数时刻 $t_i$ 到站。一辆容量无限的摆渡车负责运送，每次发车并返回共需 $m$ 分钟，上下车时间忽略。返回后可立即发车，也可以继续等候。安排各次发车时刻，让所有乘客得到运送，并使各人的等待时间总和最小。

输入格式

第一行包含两个正整数 $n, m$，以一个空格分开，分别代表等车人数和摆渡车往返一趟的时间。

第二行包含 $n$ 个非负整数，相邻两数之间以一个空格分隔，第 $i$ 个非负整数 $t_i$ 代表第 $i$ 个同学到达车站的时刻。

输出格式

输出一行，一个整数，表示所有同学等车时间之和的最小值（单位：分钟）。

样例

样例 1

输入：

5 1 
3 4 4 3 5

输出：

0

样例 2

输入：

5 5 
11 13 1 5 5

输出：

4

数据范围与特殊性质

对于 $10\%$ 的数据，$n ≤ 10$，$m = 1$，$0 ≤ t_i ≤ 100$。
对于 $30\%$ 的数据，$n ≤ 20$，$m ≤ 2$，$0 ≤ t_i ≤ 100$。
对于 $50\%$ 的数据，$n ≤ 500$，$m ≤ 100$，$0 ≤ t_i ≤ 10^4$。
另有 $20\%$ 的数据，$n ≤ 500$，$m ≤ 10$，$0 ≤ t_i ≤ 4 \times 10^6$。
对于 $100\%$ 的数据，$n ≤ 500$，$m ≤ 100$，$0 ≤ t_i ≤ 4 \times 10^6$。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

暴力退路标注（教学补充）

DP 可用暴力拿部分分。按整数时刻 DFS 决定发车/等待，状态含时刻、上次发车时刻、待接乘客；只适合极小实例。m=1 时每个到达时刻直接发车即可拿 10% 特殊数据；进一步朴素时间 DP 可面向前 50% 小时刻数据。纯 DFS 没有稳定的 30% 保证。

目标范围：10 分特殊解；DFS 不承诺固定分值。部分分按原题规模判断，不构成对任意实现或评测机的得分保证。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P5017
• 赛事：NOIP 普及组复赛（CSP-J 前身） 2018。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。