Page not loading? Try clicking here.
Placeholder

#2310

[고등부] 2024 KOI 2차대회 대비 모의고사 (3주차)

균형 배치
Subtask
5s 1024MB

Problems

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 ith 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.


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

The minimum time required to achieve the goal.


Subtask

# Score Condition
#14

Only the data in the example is given.

#26

R=2

#320

R≤10,N≤80

#430

R≤16

#540

No additional constraints


Example #1

12 2 1 2
7
26

We 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.


Example #2

12 2 1 2
10
8

We 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.


Example #3

24 4 5 2
0 15 6 9 18
30
You must sign in to write code.