{"raw_statement":[{"iden":"statement","content":"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.  \n\nYour 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$).  \n\nCompute the minimum time required to achieve the goal."},{"iden":"input","content":"The first line contains $L$, $R$, $N$, and $K$.  \n\nThe next line contains $N$ space-separated integers $a_1,a_2,\\dots,a_N$."},{"iden":"output","content":"The minimum time required to achieve the goal."},{"iden":"note","content":"##### For Sample 1:\nWe 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.  \n\n##### For Sample 2:\nWe 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.  \n\n\n#### SCORING:\n- Inputs 5-6: $R=2$.\n- Inputs 7-12: $R\\le 10, N\\le 80$.\n- Inputs 13-20: $R\\le 16$.\n- Inputs 21-24: No additional constraints."}],"translated_statement":null,"sample_group":[["10 2 1 2\n6","22"],["10 2 1 2\n7","4"],["32 4 5 2\n0 23 12 5 11","48"],["24 3 1 2\n16","48"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}