문제

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.

입력

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

The next line contains $N$ space-separated integers $a_1,a_2,\dots,a_N$.

출력

The minimum time required to achieve the goal.

예제 입력 1

10 2 1 2
6

예제 출력 1

22

예제 입력 2

10 2 1 2
7

예제 출력 2

4

예제 입력 3

32 4 5 2
0 23 12 5 11

예제 출력 3

48

예제 입력 4

24 3 1 2
16

예제 출력 4

48

점수

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.