#CW5. 访问(vis)

访问(vis)

题目描述

在一条数轴上有 nn 个点,你需要全部访问它们(即移动到它们所在的位置),起点坐标为 SS,第 ii 个位置的坐标为 xix_i。

从 SS 出发后,每秒可以沿数轴向左或向右移动一个单位。

当到达某个需要访问的点时,可以选择将该点“标记”,这个操作不消耗时间。

之后,可以在任意时刻,从已经标记的点中任选一个,并立即传送到那里。

整个过程中最多可以标记 KK 个点。

请制定一个行程,使所有给定的点都至少被访问一次,并使总用时最少。

求完成全部访问所需的最短时间。

输入格式

第一行包含三个整数 n,S,Kn, S, K,分别表示需要访问的位置数量、起点坐标以及最多可以标记的点数。

第二行包含 nn 个整数 x1,x2,…,xnx_1, x_2, \ldots, x_n,表示各个需要访问的位置的坐标。

输出格式

输出一个整数,表示访问所有位置至少一次所需的最短时间。

样例 1 输入

4 3 4
1 2 4 5

样例 1 输出

5

数据范围

对于所有测试数据,保证:1≤n≤1051 \le n \le 10^5,0≤K≤n0 \le K \le n,0≤S,xi≤1090 \le S, x_i \le 10^9。所有 SS 和 xix_i 互不相同。

测试点 n≤n \le S,xi≤S, x_i \le K≤K \le 特殊性质
1∼31 \sim 3 55 1010 nn 无
4∼64 \sim 6 10310^3 10610^6 00
7∼107 \sim 10 nn
11∼1311 \sim 13 xix_i 严格递增
14∼1614 \sim 16 10510^5 10910^9 00 无
17∼2017 \sim 20 nn