Problem Description

You and a robot start at point $0$ on a circle with a circumference of $L$ ($1 \le L \le 10^9$). You can move along the circle either clockwise or counterclockwise at a speed of $1$ unit per second. All movements in this problem are continuous.

Your goal is to place exactly $R-1$ robots such that each pair of adjacent robots is exactly $L/R$ units apart ($2 \le R \le 20$, $R$ divides $L$). There are $N$ ($1 \le N \le 10^5$) activation points, where the $i$-th activation point is located $a_i$ units counterclockwise from point $0$ ($0 \le a_i < L$). If you are at an activation point, you can place a robot immediately at that point. All robots, including the initial one, move counterclockwise at a speed of $1$ unit every $K$ seconds ($1 \le K \le 10^6$).

Calculate the minimum time required to achieve your goal.

Input Format

The first line of input contains $L$, $R$, $N$, and $K$.

The second line contains $N$ space-separated integers $a_1, a_2, \ldots, a_N$.

Output Format

Output the minimum time required to achieve the goal.

Sample Input and Output

Sample Input #1

10 2 1 2
6

Sample Output #1

22

Sample Input #2

10 2 1 2
7

Sample Output #2

4

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

Notes/Hints

Sample Explanation 1

We can reach the activation point at $6$ by moving clockwise in $4$ seconds. At this time, the initial robot will be at point $2$. We then wait $18$ seconds until the initial robot is at point $1$. Now we can place a robot to immediately win.

Sample Explanation 2

We can reach the activation point at $7$ by moving clockwise in $3$ seconds. At this time, the initial robot will be at point $1.5$. We then wait one second until the initial robot is at point $2$. Now we can place a robot to immediately win.

Test Point Properties

• Test points $5-6$: $R=2$.
• Test points $7-12$: $R \le 10, N \le 80$.
• Test points $13-20$: $R \le 16$.
• Test points $21-24$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分