30057번 - Robotai 다국어

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$