Activating Robots

Time limit5sMemory limit1024 MB

Summary

Given a circle of length L and activation points, find the minimum time for you and robots moving at speed 1/K to form R equally spaced robots.

Level: Hard8 of 10
Topics: Greedy, Binary search, Math, Implementation
Solved: No attempts yet

Problem

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 so that, at the end, every two consecutive robots are $L/R$ apart ( $2 \le R \le 20$ , and $R$ divides $L$ ). There are $N$ ( $1 \le N \le 10^5$ ) activation points. The $i$ th one is $a_i$ units counterclockwise from $0$ ( $0 \le a_i < L$ ). If you are at an activation point, you can instantly place a robot there. All robots, including the original one, move counterclockwise at a rate of $1$ unit per $K$ seconds ( $1 \le K \le 10^6$ ).

Compute the minimum time required to reach the goal.

Input

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

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

Output

Print the minimum time required to reach the goal.

Examples4

Example 1
Input
```
10 2 1 2
6
```
Expected output
```
22
```
Example 2
Input
```
10 2 1 2
7
```
Expected output
```
4
```
Example 3
Input
```
32 4 5 2
0 23 12 5 11
```
Expected output
```
48
```
Example 4
Input
```
24 3 1 2
16
```
Expected output
```
48
```