IOI2015 开幕式正在进行最后一个环节。按计划，在开幕式期间，每个代表队都将收到由主办方发放的一个装有纪念品的盒子。然而所有志愿者都被精彩的开幕式所吸引，除 Aman 以外其他人完全忘记了发放纪念品这件事。Aman 是一位热情的志愿者，为使得 IOI 尽量圆满，他要用最短的时间将所有纪念品发放出去。

开幕式的场地是一个被划分成 $L$ 个完全相等的区域的圆环，这些区域的编号依次是 $0$ 到 $L-1$，也就是说，对于 $0\le i\le L-2$，区域 $i$ 与区域 $i+1$ 相邻，且区域 $L-1$ 与区域 $0$ 相邻。场地上一共有 $N$ 个代表队，每队坐在上面的某个区域上，每个区域可以包含任意多个代表队，也可以为空。

一共有 $N$ 个相同的纪念品。一开始，Aman 和所有纪念品都在区域 $0$。Aman 应该给每队一个纪念品，并且在发放完最后一个纪念品后他必须回到区域 $0$ 。注意，有些队可能坐在区域 $0$。

Aman 可以花费 $1$ 秒的时间从一个区域移动到与他相邻的区域(顺时针或者逆时针都可以)，当 Aman 经过区域 $0$ 时他可以拿走若干纪念品，拿走纪念品是不需要时间的。任意时刻，Aman 身上只能携带不超过 $K$ 个纪念品，Aman 可以给所在区域的队伍发纪念品，这也是不需要时间的。

你的任务是：计算 Aman 从区域 $0$ 出发，给每个队伍发送纪念品并且最后回到区域 $0$ 至少需要多少时间（秒）。

样例

在这个样例中，代表队的数目 $N=3$，Aman 最多携带纪念品的数量 $K=2$，区域的数量 $L=8$。这些代表队分别位于区域 $1$，$2$和$5$。

上图是最优解之一。

第一步：Aman 在起点拿走 $2$ 个纪念品，一个发给区域 $2$，一个发给区域 $5$，然后顺便绕回到起点，刚好走了一圈，花费了 $8$ 秒钟。

第二步：Aman 在起点拿走 $1$ 个纪念品，发给区域 $1$，然后原路返回，花费了 $2$ 秒钟。

于是总用时是 $10$ 秒钟。

任务

你需要实现函数 delivery，对于给定的 $N$，$K$，$L$，以及所有代表队所在的区域，计算并返回 Aman 所需要的最短时间（秒钟）。

• delivery(N, K, L, positions)
  • N：代表队的数目
  • K：Aman每次最多能携带的纪念品数量。
  • L：开幕式场地上的区域数目。
  • positions：一个长度为 N 的数组，positions[0],positions[1]...positions[N-1]给出了所有代表队所在的区域的编号，positions的元素按非递减排序。
  • 该函数应当返回 Aman 所需要的最短时间（秒数）。

子任务

实现细节

本题只支持 C/C++。

你只能提交一个源文件实现如上所述的 delivery 函数，并且遵循下面的命名和接口。你需要包含头文件 boxes.h。

long long delivery(int N, int K, int L, int positions[]);

评测方式

评测系统将读入如下格式的输入数据：

1. 第 $1$ 行：$N$ $K$ $L$
2. 第 $2$ 行：$positions[0]...positions[N-1]$

评测系统将调用 $delivery$ 并输出它的返回值。

交互式类型的题目怎么本地测试

时间限制：$2\mathtt{\text{s}}$

空间限制：$1500\mathtt{\text{MB}}$

下载

样例及测评库下载