로봇 활성화

시간 제한5초메모리 제한1024 MB

요약

길이 L인 원 위에서 활성화 지점을 이용해 로봇 R대를 같은 간격으로 배치하는 최소 시간을 구합니다.

난이도: 어려움10점 중 8점
유형: 그리디, 이분 탐색, 수학, 구현
정답자: 아직 제출이 없습니다

문제

당신과 로봇 한 대가 둘레가 $L$ 인 원 위의 점 $0$ 에 있다 ( $1 \le L \le 10^9$ ). 당신은 원을 따라 반시계 방향이나 시계 방향으로 초당 $1$ 단위의 속도로 이동할 수 있다. 이 문제의 모든 이동은 연속적이다.

목표는 로봇을 정확히 $R-1$ 대 배치하여, 최종적으로 이웃한 두 로봇의 간격이 모두 $L/R$ 이 되게 하는 것이다 ( $2 \le R \le 20$ , $R$ 은 $L$ 의 약수이다). 활성화 지점은 $N$ 개 있다 ( $1 \le N \le 10^5$ ). $i$ 번째 지점은 $0$ 에서 반시계 방향으로 $a_i$ 만큼 떨어져 있다 ( $0 \le a_i < L$ ). 활성화 지점에 있으면 그 자리에 즉시 로봇을 놓을 수 있다. 원래 있던 로봇을 포함한 모든 로봇은 $K$ 초마다 $1$ 단위의 속도로 반시계 방향으로 움직인다 ( $1 \le K \le 10^6$ ).

목표를 달성하는 데 필요한 최소 시간을 구하라.

입력

첫 줄에 $L$ , $R$ , $N$ , $K$ 가 주어진다.

다음 줄에는 공백으로 구분된 정수 $a_1, a_2, \dots, a_N$ 이 주어진다.

출력

목표를 달성하는 데 필요한 최소 시간을 출력한다.

예제4

예제 1
입력
```
10 2 1 2
6
```
예상 출력
```
22
```
예제 2
입력
```
10 2 1 2
7
```
예상 출력
```
4
```
예제 3
입력
```
32 4 5 2
0 23 12 5 11
```
예상 출력
```
48
```
예제 4
입력
```
24 3 1 2
16
```
예상 출력
```
48
```