B. 摆渡车

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

nnn 名同学要乘坐摆渡车从人大附中前往人民大学,第 iii 位同学在第 tit_iti 分钟去等车。只有一辆摆渡车在工作,但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中(去接其他同学),这样往返一趟总共花费 mmm 分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到人民大学。

凯凯很好奇,如果他能任意安排摆渡车出发的时间,那么这些同学的等车时间之和最小为多少呢?

注意:摆渡车回到人大附中后可以即刻出发。

输入格式

第一行包含两个正整数 n,mn,mn,m,以一个空格分开,分别代表等车人数和摆渡车往返一趟的时间。
第二行包含 nnn 个正整数,相邻两数之间以一个空格分隔,第 iii 个非负整数 tit_iti 代 表第 iii 个同学到达车站的时刻。

输出格式

输出一行,一个整数,表示所有同学等车时间之和的最小值(单位:分钟)。

样例

样例输入 1

5 1 
3 4 4 3 5

样例输出 1

0

样例解释 1

同学 111 和同学 444 在第 333 分钟开始等车,等待 000 分钟,在第 333 分钟乘坐摆渡车出发。摆渡车在第 444 分钟回到人大附中。
同学 222 和同学 333 在第 444 分钟开始等车,等待 000 分钟,在第 444 分钟乘坐摆渡车出发。摆渡车在第 555 分钟回到人大附中。
同学 555 在第 555 分钟开始等车,等待 000 分钟,在第 555 分钟乘坐摆渡车出发。
自此所有同学都被送到人民大学。总等待时间为 000

样例输入 2

5 5 
11 13 1 5 5

样例输出 2

4

样例解释 2

同学 333 在第 111 分钟开始等车,等待 000 分钟,在第 111 分钟乘坐摆渡车出发。摆渡车在第 666 分钟回到人大附中。
同学 444 和同学 555 在第 555 分钟开始等车,等待 111 分钟,在第 666 分钟乘坐摆渡车出发。摆渡车在第 111111 分钟回到人大附中。
同学 111 在第 111111 分钟开始等车,等待 222 分钟;同学 222 在第 131313 分钟开始等车, 等待 000 分钟。他/她们在第 131313 分钟乘坐摆渡车出发。
自此所有同学都被送到人民大学。总等待时间为 444

可以证明,没有总等待时间小于 444 的方案。

样例 3

见附加文件中的 bus3.inbus3.ans

数据范围与提示

对于 10%10\%10% 的数据,n≤10,m=1,0≤ti≤100n \le 10, m = 1, 0 \le t_i \le 100n10,m=1,0ti100
对于 30%30\%30% 的数据,n≤20,m≤2,0≤ti≤100n \le 20, m \le 2, 0 \le t_i \le 100n20,m2,0ti100
对于 50%50\%50% 的数据,n≤500,m≤100,0≤ti≤104n \le 500, m \le 100, 0 \le t_i \le 10^4n500,m100,0ti104
另有 20%20\%20% 的数据,n≤500,m≤10,0≤ti≤4×106n \le 500, m \le 10, 0 \le t_i \le 4 \times 10^6n500,m10,0ti4×106
对于 100%100\%100% 的数据,n≤500,m≤100,0≤ti≤4×106n \le 500, m \le 100, 0 \le t_i \le 4 \times 10^6n500,m100,0ti4×106