Problem C
Tycho

Planetą tyrinėjantis robotas Tycho VIII surinko mineralų pavyzdžių ir turi grįžti į bazę. Tycho keliauja tiesia linija nuo koordinatės $0$ iki bazės, kurios koordinatė yra $b$. Tycho juda lėtu, tačiau pastoviu greičiu: per sekundę nukeliauja $1$ ilgio vienetą. Deja, planetoje sąlygos atšiaurios ir kas sekundę Tycho patiria $1$ žalos vienetą.

Situacija dar prastesnė, nes iš netoliese esančio pulsaro sklinda radiacija. Dėl šios radiacijos robotas papildomai patiria $d$ žalos vienetų kas $p$ sekundžių. Visgi radiacinės žalos galima išvengti, pakeliui pasislėpus vienoje iš $n$ skirtingų slėptuvių, esančių uolose, augmenijoje, tarp didžiulių akmenų ar planetos megafaunos griaučiuose. Tycho bet kurio metu gali nuspręsti nejudėti kiek tik nori sekundžių.

Tycho nepatiria radiacinės žalos pradinėje pozicijoje (koordinatė yra $0$) ir bazėje (koordinatė $b$), nes jos yra apsaugotos nuo radiacijos.

Kiek mažiausiai žalos Tycho patirs vykdamas atgal į bazę?

Pavyzdys

Pavyzdžiui, bazės koordinatė yra $18$, o slėptuvės yra koordinatėse $8$ ir $15$.

Tarkime, kad pulsaro periodas yra $4$, tad neapsaugotas Tycho patirtų žalos laiko momentais $4$, $8$, $12$, ir t. t. Jeigu Tycho pajudėtų iš pradinės pozicijos (kur jis yra saugus) laiko momentu $0$, tai galėtų pasiekti pirmąją slėptuvę po $8$ sekundžių, taip patirdamas radiacinės žalos $d$ laiko momentu $4$ (bet ne laiko momentu $8$, kadangi tuo metu jis vėl būtų apsaugotas). Jei judėtų nesustodamas, jis pasiektų bazę $18$-tu laiko momentu, patirdamas dar $d+d$ vienetų radiacinės žalos (laiko momentais $12$ and $16$). Šiuo atveju jis patirtų $d+d+d=3d$ vienetų radiacinės žalos ir $18$ vienetų žalos iš aplinkos.

Tačiau jei Tycho palauktų $2$-ojoje slėptuvėje (kurios koordinatė $15$) vieną sekundę, tai pulsas laiko momentu $16$ nepadarytų jam jokios žalos. Tuomet Tycho pasiektų bazę $19$-tu laiko momentu, iš viso patyręs $2d + 19$ vienetų žalos. Tai būtų geresnis variantas daugumai $d$ reikšmių. Šios dvi situacijos pavaizduotos čia:

Jeigu pulsaro periodas yra $10$, Tycho galėtų laukti pradinėje pozicijoje $2$ sekundes ir tuomet judėti į bazę nesustodamas. Taip Tycho praeitų $1$-ąją slėptuvę (kurios koordinatė yra $8$) būtent tuo metu, kai pulsaras supulsuotų, ir atvyktų į bazę laiko momentu $20$, iš viso patirdamas $20$ vienetų žalos iš aplinkos ir nepatirdamas jokios radiacinės žalos.

Pradiniai duomenys

Pirmoje eilutėje pateikti tarpais atskirti keturi sveikieji skaičiai $b$, $p$, $d$ ir $n$: bazės koordinatė $b$, pulsaro pulsavimo periodas $p$, radiacinė žala $d$, padaroma kiekvieno pulsavimo metu, slėptuvių skaičius $n$.

Kitose $n$ eilučių pateikta po sveikąjį skaičių – slėptuvių koordinatės $a_1$, $\ldots $, $a_ n$, kurioms galioja $0<a_1<\cdots <a_ n< b$.

Rezultatas

Išspausdinkite vieną sveikąjį skaičių: kiek mažiausiai žalos vienetų patirs Tycho, norėdamas pasiekti bazę ties koordinate $b$.

Ribojimai ir vertinimas

Visada galios $p < b$ ir $n < b$. Taip pat galios ribojimai $1\leq b\leq 10^{12}$, $0\leq d \leq 10^6$ ir $0\leq n \leq 10^5$.

Jūsų sprendimas bus testuojamas su keliomis testų grupėmis, kurių kiekviena verta tam tikro skaičiaus taškų. Kiekviena testų grupė sudaryta iš įvairių testų. Testų grupės taškai skiriami tik išsprendus visus grupės testus. Jūsų sprendimo surinktas taškų skaičius lygus daugiausiai surinkusio sprendimo taškų skaičiui.

$^*$ Testų grupėje $1$ Tycho gali tekti palaukti ties koordinate $0$ prieš jam pajudant. Pavyzdžiui, žemiau pateikti $2$-asis, $3$-iasis ir $4$-asis pavyzdžiai priklauso $1$-ajai testų grupei.

18 4 5 2
8
15

29

18 4 0 2
8
15

18

18 10 100 2
8
15

20

18 4 100 0

418

65 20 100 3
14
25
33

172