Robots on a Moving Circle

You are standing at point 0 on a circle of circumference L (1 ≤ L ≤ 10^9). A robot is also initially at point 0. You can move continuously along the circle at speed 1 unit per second, in either the clockwise or counterclockwise direction.

There are N activation points on the circle; the i-th activation point is located at a distance of a_i (with 0 ≤ a_i < L) measured in the counterclockwise direction from point 0. When you arrive at an activation point, you may immediately place a robot there. In total, you must place exactly R-1 additional robots (2 ≤ R ≤ 20, and R divides L). At the final moment, there will be R robots (including the initial one).

Once placed, all robots (including the initial one) move continuously in the counterclockwise direction at a speed of 1 unit per K seconds (1 ≤ K ≤ 10^6). Your objective is to achieve a configuration in which the robots lie equally spaced – that is, the distance along the circle between any two consecutive robots is exactly L/R units.

Because the robots move after being placed, if a robot is placed at an activation point x at time t, then at the final time T its position will be

The intended final configuration is an arithmetic progression modulo L. In particular, if we denote the final positions by

then the already placed robot (from time 0 at position 0) will finish at \(\frac{T}{K}\) and must take one of these positions; the remaining robots you place (in some order) must finish at the remaining positions. In fact, one may show that if a robot is placed at an activation point x as the robot corresponding to an order index j (with indices chosen so that the R final positions are in order), then a necessary and sufficient condition for the configuration to be valid is that

It turns out that the earliest time at which you can complete the task is determined by the time at which you are able to visit a suitable sequence of activation points in order (either going in the counterclockwise direction or in the clockwise direction) while matching the time‐requirements given by the robot motion. More precisely, if you plan to assign the robot placed at the i-th visitation to slot j (for j = 1, 2, ..., R-1) then by rearranging the equation above one may deduce that the ideal placement time should be

[ t = K\Bigl(x - j\cdot\frac{L}{R}\Bigr) \quad (\text{mod } K,L). ]

Since you might have to wait for the ideal moment (and you cannot arrive before you physically travel there), the actual placement time at an activation point x when aiming for slot j is the smallest time not less than your arrival time that is congruent (in \(K\,L\)) to \(K(x - j\,L/R)\). Your task is to compute the minimum possible time T such that by visiting activation points in one of the two directions you can place robots to achieve the equally‐spaced final configuration.

Input and output details: Because of the two possible directions (counterclockwise and clockwise), an optimal strategy may involve going either way around the circle – you should compute the best possible overall time.

inputFormat

The first line contains four integers: L, R, N, and K.

The second line contains N integers: a₁, a₂, ..., a_N, where each a_i (0 ≤ a_i < L) represents an activation point measured in the counterclockwise direction from point 0.

Note: It is guaranteed that R divides L and that 2 ≤ R ≤ 20, 1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 10⁶, 1 ≤ L ≤ 10⁹.

outputFormat

Output a single integer: the minimum time T needed to achieve the goal configuration.

sample

12 3 3 2
0 4 8

4