Problem 3. Activating Robots

USACO 2024 US Open Contest, Platinum

你和一个机器人初始时位于周长为 $L$（$1 \le L \le 10^9$）的圆上的点 $0$ 处。你可以以每秒 $1$ 单位的速度沿圆周顺时针或逆时针移动。本题中的所有移动都是连续的。

你的目标是放置恰好 $R-1$ 个机器人，使得最终每两个相邻的机器人彼此相距 $L/R$（$2\le R\le 20$，$R$ 整除 $L$）。有 $N$（$1\le N\le 10^5$）个激活点，其中第 $i$ 个激活点位于距点 $0$ 逆时针方向 $a_i$ 距离处（$0\le a_i<L$）处。如果你当前位于一个激活点，你可以立刻在该点放置一个机器人。所有机器人（包括初始的）均以每 $K$ 秒 $1$ 单位的速度逆时针移动（$1\leq K\leq 10^6$）。

计算达到目标所需要的最小时间。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $L$，$R$，$N$ 和 $K$。

第二行包含 $N$ 个空格分隔的整数 $a_1,a_2,\dots,a_N$。

输出格式（输出至终端 / 标准输出）：

输出达到目标所需要的最小时间。

输入样例：

10 2 1 2
6

输出样例：

22

我们可以通过顺时针移动在 $4$ 秒内到达点 $6$ 的激活点。此时，初始的机器人将位于点 $2$。再等待 $18$ 秒直到初始机器人位于点 $1$。现在我们可以放置一个机器人以立即获胜。

输入样例：

10 2 1 2
7

输出样例：

4

我们可以通过顺时针移动在 $3$ 秒内到达点 $7$ 的激活点。此时，初始的机器人将位于点 $1.5$。再等待一秒直到初始机器人位于点 $2$。现在我们可以放置一个机器人以立即获胜。

输入样例：

32 4 5 2
0 23 12 5 11

输出样例：

48

输入样例：

24 3 1 2
16

输出样例：

48

测试点性质： 测试点 5-6：$R=2$。测试点 7-12：$R\le 10, N\le 80$。测试点 13-20：$R\le 16$。测试点 21-24：没有额外限制。

供题：Benjamin Qi