Problem C
Tycho

Das Planetenerkundungsfahrzeug Tycho VIII muss nach dem Sammeln von Mineralproben zur Heimatbasis zurückkehren. Tycho bewegt sich in einer geraden Linie von Position $0$ zur Heimatbasis an Position $b$. Dabei bewegt es sich mit einer langsamen, aber stetigen Geschwindigkeit von $1$ Einheit pro Sekunde vorwärts. Jede Sekunde erleidet Tycho $1$ Einheit an Umweltschaden durch die rauen Bedingungen des Planeten.

Die Situation wird durch die Strahlung eines nahe gelegenen Pulsars noch verschlimmert, der alle $p$ Sekunden $d$ zusätzliche Einheiten Schaden verursacht. Der Strahlungsschaden kann jedoch vermieden werden, indem man in einem von $n$ verschiedenen Verstecken auf dem Weg Schutz sucht - Höhlen, Vegetation, große Felsen, Kadaver der Megafauna des Planeten. Tycho kann sich entscheiden, an einem beliebigen Punkt für eine beliebige ganze Zahl an Sekunden stillzustehen.

Die Startposition $0$ und die Heimatbasis bei $b$ sind beide geschützt, so dass Tycho dort keinen Strahlungsschaden erleidet.

Wie hoch ist der minimale Schaden, den Tycho auf seiner Reise zurück zur Heimatbasis erleiden wird?

Beispiel

Betrachten wir die Situation, in der sich die Heimatbasis an der Position $18$ befindet und es Schutzräume an den Positionen $8$ und $15$ gibt.

Nehmen wir an, dass die Periode des Pulsars $4$ beträgt, so dass Tycho ohne Schutz zum Zeitpunkt $4$, $8$, $12$ usw. Schaden nehmen würde. Wenn Tycho von der Startposition (wo es geschützt ist) zum Zeitpunkt $0$ aufbricht, kann es den ersten Schutzraum nach $8$ Sekunden erreichen, wobei es zum Zeitpunkt $4$ Strahlungsschaden $d$ erleidet (aber keinen zum Zeitpunkt $8$, weil es dann geschützt ist). Setzt es seinen Weg fort, ohne anzuhalten, erreicht es die Heimatbasis zum Zeitpunkt $18$, wobei es $d+d$ weitere Einheiten Strahlungsschaden erleidet (zum Zeitpunkt $12$ bzw. $16$). Auf diese Weise erleidet es $d+d+d=3d$ Einheiten Strahlungsschaden und $18$ Einheiten Umweltschaden. Wenn Tycho stattdessen am $2$-ten Bunker (an der Position $15$) eine Sekunde lang wartet, verursacht das Aufblitzen des Pulsars zum Zeitpunkt $16$ keinen Schaden, und es erreicht die Heimatbasis zum Zeitpunkt $19$ mit insgesamt $2d + 19$ Schadenseinheiten. Dies ist für die meisten Werte von $d$ besser. Die beiden Situationen sind hier dargestellt:

Wenn der Pulsar eine Periode von $10$ hat, kann Tycho an der Startposition $2$ Sekunden lang warten und dann einfach nach Hause fahren, ohne an einem Schutzraum anzuhalten. Auf diese Weise passiert es den $1$-ten Schutzraum (an Position $8$) genau im richtigen Moment, wenn der Pulsar aufblitzt, und erreicht die Heimatbasis zur Zeit $20$, wobei es insgesamt $20$ Umwelt- und keinen Strahlungsschaden erleidet.

Eingabe

Die erste Zeile besteht aus vier ganzen Zahlen $b$, $p$, $d$ und $n$, die durch einzelne Leerzeichen getrennt sind: dem Standort $b$ der Heimatbasis, die Periode des Pulsars $p$, der zusätzliche Strahlungsschaden $d$, der durch jedes Aufblitzen des Pulsars verursacht wird, und die Anzahl $n$ der Schutzräume. Die folgenden $n$ Zeilen enthalten jeweils eine ganze Zahl, die die Standorte der Schutzräume $a_1$, $\ldots $, $a_ n$ angeben, wobei $0<a_1<\cdots <a_ n< b$.

Ausgabe

Gib eine einzelne ganze Zahl aus: die Mindestmenge an Schaden, die Tycho erleiden muss, um $b$ zu erreichen.

Beschränkungen und Bewertung

Du kannst annehmen, dass $p < b$ und $n < b$. Es gilt immer $1\leq b\leq 10^{12}$, $0\leq d \leq 10^6$, und $0\leq n \leq 10^5$.

Deine Lösung wird an einer Reihe von Testgruppen getestet, von denen jede eine bestimmte Anzahl von Punkten wert ist. Jede Testgruppe enthält eine Reihe von Testfällen. Um die Punkte für eine Testgruppe zu erhalten, musst du alle Testfälle in der Testgruppe lösen. Deine endgültige Punktzahl ist die maximale Punktzahl für eine einzelne Einsendung.

$^*$ In der Testgruppe $1$ muss Tycho möglicherweise noch an der Position $0$ warten, bevor es sich in Bewegung setzt. Zum Beispiel gehören die Beispieleingaben $2$, $3$ und $4$ zur 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