Problem C
Tycho

Pojazd do eksploracji planet Tycho VIII musi wrócić do bazy macierzystej po zebraniu próbek minerałów. Tycho podróżuje w linii prostej z pozycji $0$ do bazy domowej na pozycji $b$. Podczas ruchu posuwa się do przodu w wolnym, ale stałym tempie $1$ jednostki na sekundę. W każdej sekundzie Tycho ponosi $1$ jednostkę szkód środowiskowych spowodowanych trudnymi warunkami panującymi na planecie.

Sytuację pogarsza jeszcze promieniowanie z pobliskiego pulsara, które dodaje $d$ dodatkowych jednostek obrażeń co $p$ sekund. Obrażeń od promieniowania można jednak uniknąć, szukając schronienia w jednej z $n$ różnych kryjówek — jaskiniach, roślinności, dużych skałach, padlinach megafauny planety — po drodze. Tycho może zdecydować się na stanie w miejscu przez dowolną liczbę całkowitą sekund.

Pozycja startowa $0$ i baza domowa $b$ są osłonięte, więc Tycho nie otrzymuje tam żadnych obrażeń od promieniowania.

Jaka jest najmniejsza sumaryczna liczba obrażeń otrzymanych przez Tycho w drodze powrotnej do bazy?

Przykład

Rozważ sytuację, w której baza macierzysta znajduje się na pozycji $18$, a na pozycjach $8$ i $15$ znajdują się schrony.

Przyjmij, że okres pulsara to $4$, więc Tycho poza schronieniem odbierałby obrażenia w momentach $4$, $8$, $12$, itd. Jeśli Tycho wyjdzie z pozycji startowej (gdzie jest osłonięty) w czasie $0$, może dotrzeć do pierwszego schronu po $8$ sekundach, ponosząc obrażenia od promieniowania $d$ w czasie $4$ (ale żadnych w czasie $8$, ponieważ jest wtedy osłonięty). Kontynuując bez zatrzymywania się, dociera do bazy domowej w czasie $18$, ponosząc $d+d$ kolejnych jednostek obrażeń od promieniowania (odpowiednio w czasie $12$ i $16$). W ten sposób ponosi $d+d+d=3d$ jednostek obrażeń od promieniowania i $18$ jednostek obrażeń od środowiska. Jeśli zamiast tego Tycho czeka w schronie o numerze $2$ (na pozycji $15$) przez $1$ sekundę, impuls w czasie $16$ nie powoduje żadnych obrażeń, a do bazy macierzystej dociera w czasie $19$ z łączną liczbą $2d + 19$ jednostek obrażeń. Jest to lepsze rozwiązanie dla większości wartości $d$. Te dwie sytuacje są pokazane tutaj:

Jeśli okres pulsara wynosi $10$, Tycho może czekać na pozycji startowej przez $2$ sekundy, a potem po prostu wrócić do domu, nie zatrzymując się w żadnym schronie. W ten sposób mija schron o numerze $1$ (na pozycji $8$) we właściwym momencie, gdy pulsar rozbłyska i dociera do bazy macierzystej w czasie $20$, za łączną sumę $20$ szkód środowiskowych i żadnych szkód radiacyjnych.

Wejście

Pierwsza linia składa się z czterech liczb całkowitych $b$, $p$, $d$, oraz $n$, oddzielonych pojedynczymi spacjami: lokalizacji bazy domowej $b$, okresu rozbłysku pulsara $p$, dodatkowych szkód radiacyjne $d$ spowodowane przez każdą flarę pulsara, oraz liczby schronów $n$. Kolejne $n$ wierszy zawierają po jednej liczbie całkowitej oznaczającej lokalizacje schronów $a_1$, $\ldots $, $a_ n$, spełniające $0<a_1<\cdots <a_ n< b$.

Wyjście

Wypisz pojedynczą liczbę całkowitą: minimalną ilość obrażeń, jakie musi przyjąć Tycho, by dotrzeć na pozycję $b$.

Ograniczenia i punktacja

Możesz założyć $p < b$ oraz $n < b$. Zawsze jest spełnione $1\leq b\leq 10^{12}$, $0\leq d \leq 10^6$, oraz $0\leq n \leq 10^5$.

Twoje rozwiązanie zostanie przetestowane na zestawie grup testowych, z których każda jest warta pewną liczbę punktów. Każda grupa testowa zawiera zestaw przypadków testowych. Aby uzyskać punkty za grupę testową musisz rozwiązać wszystkie przypadki testowe w tej grupie. Twój ostateczny wynik będzie maksymalnym wynikiem pojedynczego zgłoszenia.

$^*$ W grupie testowej $1$, Tycho może nadal potrzebować czekać na pozycji $0$ zanim zacznie się poruszać. Na przykład, przykładowe wejścia $2$, $3$, oraz $4$ należą do grupy testowej $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