上色的纱雾

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

纱雾画画功力首屈一指,现在她准备上色了,这时候她在想,怎样上色的时间最短呢?

 

3916-1

 

在这里我们把问题简化,平面图抽象成坐标轴,需要上色的地方抽象成 n 个点,纱雾有 m 支画笔。

开始的时候纱雾可以选择让画笔落在坐标轴任意一点上,之后每次移动画笔一个单位的距离都会花费 1 秒(画笔可以左右移动,纱雾强大的能力可以同时移动 m 枝画笔,涂色的时间忽略不计)。现在纱雾想要知道这 n 个点全部上完色最少要多少时间呢?

相信你一定能让可爱的纱雾露出这样的表情的:

 

3916-2

Input

多组输入。

对于每组数据:

  • 首先输入两个以空格分隔的整数 n, m (1 <= n, m <= 10^5),分别表示需要上色的点以及纱雾拥有的画笔的数量
  • 接下来一行是 n 个以空格分隔的整数(绝对值保证不超过 10^9)

Output

对于每组数据,输出一个整数,表示纱雾需要的最少时间(秒)。

Sample Input

3 2
1 4 8
3 1
1 2 9
4 2
1 2 3 6

Sample Output

3
8
2

Hint

两支画笔,第一支画笔初始地点选择 1,第二支画笔初始地点选择地点 8。

那么 3s 后第一支画笔可以到达地点 4,这样 3 个点就可以全部涂上了。

Source

【“师创杯”山东理工大学第九届ACM程序设计竞赛 热身赛】UMR