当前没有测试数据。

一、Problem Name

Activating Robots

二、Problem Description

You and a single robot are initially at point $0$ on a circle with perimeter $L$ ($1\leq L\leq10^9$). You can move either counterclockwise or clockwise along the circle at $1$ unit per second. All movement in this problem is continuous.

Your goal is to place exactly $R - 1$ robots such that at the end, every two consecutive robots are spaced $\frac{L}{R}$ away from each other ($2\leq R\leq20$, $R$ divides $L$). There are $N$ ($1\leq N\leq10^5$) activation points, the $i$th of which is located $a_i$ distance counterclockwise from $0$ ($0\leq a_i<L$). If you are currently at an activation point, you can instantaneously place a robot at that point. All robots (including the original) move counterclockwise at a rate of $1$ unit per $K$ seconds ($1\leq K\leq10^6$).

Compute the minimum time required to achieve the goal.

三、Input Format (input arrives from the terminal / stdin)

1. The first line contains $L$, $R$, $N$, and $K$.
2. The next line contains $N$ space-separated integers $a_1,a_2,\cdots,a_N$.

四、Output Format (print output to the terminal / stdout)

The minimum time required to achieve the goal.

五、Sample Input and Output

Sample Input 1

10 2 1 2
6

Sample Output 1

22

Explanation: We can reach the activation point at $6$ in $4$ seconds by going clockwise. At this time, the initial robot will be located at $2$. Wait an additional $18$ seconds until the initial robot is located at $1$. Now we can place a robot to immediately win.

Sample Input 2

10 2 1 2
7

Sample Output 2

4

Explanation: We can reach the activation point at $7$ in $3$ seconds by going clockwise. At this time, the initial robot will be located at $1.5$. Wait an additional second until the initial robot is located at $2$. Now we can place a robot to immediately win.

Sample Input 3

32 4 5 2
0 23 12 5 11

Sample Output 3

48

Sample Input 4

24 3 1 2
16

Sample Output 4

48

六、Scoring Rules

1. Inputs 5 - 6: $R = 2$.
2. Inputs 7 - 12: $R\leq10$, $N\leq80$.
3. Inputs 13 - 20: $R\leq16$.
4. Inputs 21 - 24: No additional constraints.

Problem credits: Benjamin Qi.