题目描述

有 $n$ 个人，第 $i$ 个人要到达 $a_i$ 号城市，第 $i$ 个人初始时在 $i$ 号城市。

有一辆公交车，同一时刻能承载 $w$ 个人。

公交车可以用 $1$ 个单位时间移动一个城市，向左或向右。

如果在顾客没有到达目的地时扔掉顾客，顾客会给出差评影响工资，但是我们可以暂时无视顾客，之后再接上顾客。

公交车要从起始站 $0$ 号城市开始，终点站 $n + 1$ 号城市结束，并满足所有顾客的需求。

问最短下班时间（最快送完所有顾客并回到终点站的时间）。

输入格式

第一行两个正整数 $n , w$。

接下来一行 $n$ 个正整数 $a_i$。

输出格式

一行一个整数表示答案。

样例 #1

样例输入 #1

5 1
2 3 4 5 6

样例输出 #1

6

样例 #2

样例输入 #2

5 4
2 3 4 6 6

样例输出 #2

6

样例 #3

样例输入 #3

5 5
2 4 4 5 6

样例输出 #3

6

点我下载大样例

样例 $4, 5 , 6 , 7 , 8$ 分别满足测试点编号为 $1 , 2 , 6 , 11,13$ 的性质，特别地，样例 $6$ 同时满足测试点编号为 $8$ 的性质，样例 $8$ 同时满足测试点编号为 $17$ 的性质。

提示

测试点编号	$n \le$	$w=$	特殊性质
$1$	$10^6$	$n$	无
$2 , 3$	$10$	$1$
$4 , 5$	$18$
$6 , 7$	$10^3$
$8$	$10^5$		$a_i$ 构成等差数列
$9 , 10$	$10^6$		无
$11 ,12$	$10$	$n - 1$
$13 , 14$	$10^3$
$15 , 16$	$10^6$		$\max a_i - \min a_i \le 100 , \min a_i \ge 5 \times 10^{8}$
$17 , 18$			$n \ge 100$，$a_i$ 互不相同
$19 , 20$			无

对于 $100\%$ 的数据，$2\le n \le 10^6$，$1\le i < a_i \le 10^9$，$w \in \{1 , n - 1 , n\}$。