Robotai

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

요약

길이 L인 고랑 양 끝에서 두 로봇이 출발해 주어진 위치에 묘목을 심을 때, 심는 데 S만큼 걸린다면 모든 묘목을 심는 최소 시간을 구한다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

Iškasta tiesi $L$ ilgio vaga, kurioje reikia pasodinti $M$ medelių. Medelius sodins robotai, todėl visi atstumai vagoje matuojami robopėdomis.

Duota pozicijų (t. y. atstumų nuo vagos pradžios) seka $P\_1, P\_2, \dots , P\_M$ . Kiekvienoje šių pozicijų turi būti pasodintas vienas medelis.

Darbą turi atlikti $2$ robotai. Kiekvienas robotas per $1$ laiko vienetą nuvažiuoja $1$ robopėdą, o per $S$ laiko vienetų pasodina vieną medelį.

Per kiek mažiausiai laiko galima pasodinti visus medelius, jeigu dirbs abu robotai? Pirmojo roboto pradinė pozicija yra $0$ , o antrojo – $L$ . Abu robotai darbą pradeda tuo pačiu laiko momentu $0$ .

Duotas medelių skaičius $M$ , vagos ilgis $L$ , bei laikas, per kurį robotas pasodina vieną medelį $S$ . Taip pat duotas pozicijų, surikiuotų didėjimo tvarka, sąrašas $P\_1, P\_2, \dots , P\_M$ .

Parašykite programą, kuri apskaičiuotų trumpiausią sodinimo laiką T, per kurį robotai gali pasodinti visus medelius.

입력

Pirmojoje eilutėje pateikti trys sveikieji skaičiai: $M$ – pozicijų skaičius, $L$ – vagos ilgis, $S$ – vieno medelio sodinimo laikas.

Likusiose $M$ eilučių pateiktos medelių sodinimo pozicijos $P\_1, P\_2, \dots , P\_M$ – po vieną sveikąjį skaičių kiekvienoje eilutėje.

출력

Pirmojoje (ir vienintelėje) eilutėje išveskite trumpiausią sodinimo laiką T.

제한

$1 ≤ M ≤ 10^6$
$1 ≤ L ≤ 10^9$
$1 ≤ S ≤ 10^3$
$0 ≤ P\_i ≤ L$

예제3

예제 1
입력
```
3 8 1
1
3
6
```
예상 출력
```
5
```
예제 2
입력
```
5 5 2
1
2
3
4
5
```
예상 출력
```
8
```
예제 3
입력
```
3 17 3
0
2
4
```
예상 출력
```
13
```