← 返回题目列表

Codeforces · 958/E2

E2. 警卫职责(中)

中文机器翻译题面 查看原题

海蒂公主决定亲自向她的所有 K 叛军舰艇指挥官下达命令。不幸的是,她目前正在穿越超空间,并且只会在 N 个特定时刻 t1,t2,...,tN 离开它。因此,与指挥官的会议必须在这些时间开始和结束。也就是说,每个指挥官将在某个时间 ti 登船,并在稍后的某个时间 tj 下船。当然,海蒂需要与所有指挥官会面,并且不能同时召开两次会议。两名指挥官甚至无法在超空间跳跃的开始/结束处相遇,因为一个位置上有太多船只可能会将其坐标泄露给敌人。

你的任务是找到海蒂公主在满足上述条件的情况下花在会议上的最短时间。

输入

第一行包含两个整数 K, N (2 ≤ 2K ≤ N ≤ 500000, K ≤ 5000)。第二行包含 N 个不同的整数 t1, t2, ..., tN (1 ≤ ti ≤ 109),表示海蒂离开超空间的时间。

输出

只输出一个整数:会议所花费的最短时间。

示例

输入 #1

2 5
1 4 6 7 12

输出 #1

4

输入 #2

3 6
6 3 4 2 5 1

输出 #2

3

输入 #3

4 12
15 7 4 19 3 30 14 1 5 23 17 25

输出 #3

6

注意

在第一个示例中,有五个有效计划:[1, 4]、[6, 7],总时间为 4、[1, 4]、[6, 12],总时间为 9、[1, 4]、[7, 12],总时间为 8、[1, 6]、[7, 12],总时间为 10,以及 [4, 6]、[7, 12] 总时间为 7。所以答案是 4。

在第二个示例中,只有 1 个有效计划:[1, 2]、[3, 4]、[5, 6]。

对于第三个示例,总时间为 6 的一种可能的调度是:[1, 3]、[4, 5]、[14, 15]、[23, 25]。