Activating Robots

문제

You and a single robot are initially at point $00$ on a circle with perimeter $LL$ ($1\le L\le {10}^{9}1\; \backslash le\; L\; \backslash le\; 10^9$). You can move either counterclockwise or clockwise along the circle at $11$ unit per second. All movement in this problem is continuous.

Your goal is to place exactly $R-1R-1$ robots such that at the end, every two consecutive robots are spaced $L\mathrm{/}RL/R$ away from each other ($2\le R\le 202\backslash le\; R\backslash le\; 20$, $RR$ divides $LL$). There are $NN$ ($1\le N\le {10}^{5}1\backslash le\; N\backslash le\; 10^5$) activation points, the $ii$th of which is located $a_{i}a\_i$ distance counterclockwise from $00$ (). 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 $11$ unit per $KK$ seconds ($1\le K\le {10}^{6}1\backslash leq\; K\backslash leq\; 10^6$).

Compute the minimum time required to achieve the goal.

입력

The first line contains $LL$, $RR$, $NN$, and $KK$.

The next line contains $NN$ space-separated integers $a_1,a_2,\dots ,a_{N}a\_1,a\_2,\backslash dots,a\_N$.

출력

The minimum time required to achieve the goal.