Problem C
Tycho

Rumudforskningskøretøjet Tycho VIII skal tilbage til hjemmebasen efter at have indsamlet mineralprøver. Tycho bevæger sig i en lige linje fra position $0$ til hjemmebasen ved position $b$. Når den bevæger sig, flytter den sig med en langsom, men stabil hastighed på $1$ enhed pr. sekund. Hvert sekund tager Tycho $1$ enhed miljøskade fra de barske forhold på planeten.

Situationen forværres desuden af strålingen fra en nærliggende pulsar, der tilføjer $d$ yderligere enheder af skade hvert $p$’te sekund. Strålingsskaderne kan dog undgås ved at søge ly i de $n$ forskellige skjulesteder langs vejen – huler, vegetation, store sten, skeletter af planetens megafauna, osv. Tycho kan vælge at stå stille på vilkårlige tidspunkter i et vilkårligt antal sekunder.

Startpositionen $0$ og hjemmebasen ved $b$ gælder begge sum skjulested, så Tycho tager ingen strålingsskader der.

Hvad er den mindste mængde skade, Tycho vil tage på sin rejse tilbage til hjemmebasen?

Eksempel

Betragt situationen, hvor hjemmebasen er ved position $18$, og der er skjulesteder ved positionerne $8$ og $15$.

Antag at pulsarens periode er $4$, så Tycho ville tage skade på tidspunkterne $4$, $8$, $12$, osv., hvis den ikke er i ly. Hvis Tycho forlader startpositionen (hvor den er i ly) på tidspunkt $0$, kan den nå det første skjulested efter $8$ sekunder og blive strålingsskadet på tidspunkt $4$ (men ikke på tidspunkt $8$, idet den er i ly). Fortsætter den uden at stoppe, ankommer den til hjemmebasen på tidspunkt $18$ og pådrager sig $d+d$ flere enheder af strålingsskade (på tidspunkterne $12$ og $16$, henholdsvis). På denne måde vil den samlet pådrage sig $d+d+d=3d$ enheder af strålingsskader og $18$ enheder af miljøskader. Hvis Tycho i stedet venter ved det $2$. skjulested (ved position $15$) i $1$ sekund, forårsager pulsen på tidspunkt $16$ ingen skade, og Tycho når hjemmebasen på tidspunkt $19$ med et samlet antal skader på $2d + 19$. Dette er bedre for de fleste værdier af $d$. De to situationer er vist her:

Hvis pulsarens periode er $10$, kan Tycho vente ved startpositionen i $2$ sekunder og derefter bare køre hjem uden at standse ved nogen skjulesteder. Dermed passerer han det første skjulested (på position $8$) præcis på det rigtige tidspunkt, når pulsaren blusser op, og ankommer til hjemmebasen på tidspunkt $20$, med i alt $20$ enheder miljøskade og ingen strålingsskade overhovedet.

Indlæsning

Den første linje består af fire heltal $b$, $p$, $d$, og $n$, adskilte af enkelt mellemrum: hjemmebasens placering $b$, pulsarens periode $p$, den ekstra strålingsskade $d$ forårsaget af pulsaren og antallet $n$ af skjulesteder. De følgende $n$ linjer indeholder hvert et heltal, der angiver skjulestedernes placeringer $a_1$, $\ldots $, $a_ n$, med $0<a_1<\cdots <a_ n< b$.

Udskrift

Udskriv et enkelt heltal: det mindste mængde skader, Tycho skal tage for at nå $b$.

Begrænsninger og pointgivning

Du kan antage, at $p < b$ og $n < b$. Der gælder altid $1\leq b\leq 10^{12}$, $0\leq d \leq 10^6$ og $0\leq n \leq 10^5$.

Din løsning vil blive testet på en række testgrupper, hver med en vist antal point. Hver testgruppe indeholder en række testfald. For at opnå point for en testgruppe skal du løse alle testfald i testgruppen. Din endelige score vil være den højeste score for en enkelt indsendelse.

$^*$ I testgruppe $1$ kan Tycho godt skulle vente ved position $0$, inden den begynder at køre. Eksemplerne $2$, $3$ og $4$ tilhører testgruppe $1$.

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