platinum_Activating_Robots (USACO US_Open_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: greedy, mathematics, bitmask, dynamic programming

You and a single robot are initially at point $0$ on a circle with perimeter $L$
($1 \le L \le 10^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 $L/R$ away from each other ($2\le R\le 20$, $R$
divides $L$). There are $N$ ($1\le N\le 10^5$) activation points, the $i$th of
which is located $a_i$ distance counterclockwise from $0$ ($0\le 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\leq 10^6$).
Compute the minimum time required to achieve the goal.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains $L$, $R$, $N$, and $K$.
The next line contains $N$ space-separated integers $a_1,a_2,\dots,a_N$.
OUTPUT FORMAT (print output to the terminal / stdout):
The minimum time required to achieve the goal.
SAMPLE INPUT:
10 2 1 2
6
SAMPLE OUTPUT:
22
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:
10 2 1 2
7
SAMPLE OUTPUT:
4
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:
32 4 5 2
0 23 12 5 11
SAMPLE OUTPUT:
48
SAMPLE INPUT:
24 3 1 2
16
SAMPLE OUTPUT:
48
SCORING:
Inputs 5-6: $R=2$
Inputs 7-12: $R\le 10, N\le 80$
Inputs 13-20: $R\le 16$
Inputs 21-24: No additional constraints.
Problem credits: Benjamin Qi

Starter code:

Grader code:

Setup script:

Evaluation script: