Problem C
Tycho

Planeetantutkimusmönkijän Tycho VIII:n täytyy palata takaisin tukikohtaansa kerättyään mineraalinäytteitä. Tycho liikkuu suoralla viivalla pisteestä $0$ tukikohtaan pisteessä $b$. Se liikkuu eteenpäin hitaalla mutta varmalla $1$ yksikön nopeudella. Joka sekunti Tycho ottaa $1$ yksikön ympäristövahinkoa planeetan ankarien olosuhteiden takia.

Tilannetta pahentaa vielä lisää se, että läheisestä pulsarista tulee säteilyä, joka aiheuttaa $d$ yksikköä lisävahinkoa $p$:n sekunnin välein. Säteilyvahingon voi kuitenkin välttää etsimällä suojaa yhdestä $n$:stä eri piilopaikasta—luolista, kasvillisuudesta, suurista kivistä, planeetan megafaunan raadoista—matkan aikana. Tycho voi valita pysyä paikallaan missä tahansa kokonaislukumäärän sekunteja.

Sekä alkupiste $0$ että tukikohta $b$ ovat suojattuja, joten Tycho ei saa säteilyvahinkoa niissä ollessaan.

Mikä on pienin määrä vahinkoa, jonka Tycho voi saada matkallaan tukikohtaan?

Esimerkki

Tarkastellaan tilannetta, jossa tukikohta on kohdassa $18$ ja suojia on kohdissa $8$ ja $15$.

Oletetaan, että pulsarin jaksonaika on $4$, eli suojaamaton Tycho saisi vahinkoa hetkillä $4$, $8$, $12$, jne. Jos Tycho lähtee alkupisteestä (jossa se on suojassa) hekellä $0$, niin se voi saavuttaa ensimmäisen suojan $8$ sekunnissa, kerryttäen $d$ yksikköä säteilyvahinkoa hetkellä $4$ (mutta ei yhtään hetkellä $8$ koska se on silloin suojassa). Jatkaen pysähtymättä, se saavuttaa tukikohdan hetkellä $18$, kerryttäen $d+d$ yksikköä lisää säteilyvahinkoa (hetkillä $12$ ja $16$). Tällä tavoin se kerryttää $d+d+d=3d$ yksikköä säteilyvahinkoa ja $18$ yksikköä ympäristövahinkoa. Jos taas Tycho odottaa $2.$ suojassa (kohdassa $15$) $1$ sekunnin, niin hetken $16$ pulssi ei aiheuta sille vahinkoa, vaan se pääsee tukikohtaan hetkellä $19$ saaden yhteensä $2d + 19$ yksikköä vahinkoa. Tämä on parempi suurimmalle osalle $d$:n mahdollisista arvoista. Nämä kaksi tilannetta on esitetty tässä:

Jos pulsarin jaksonaika on $10$, niin Tycho voi odottaa alkupisteessä $2$ sekuntia ja sitten vain mennä tukikohtaan pysähtymättä mihinkään suojaan. Silloin se ohittaa $1.$ suojan (kohdassa $8$) juuri oikealla hetkellä, kun pulsarin purkaus tapahtuu, ja saapuu tukikohtaan hetkellä $20$, saaden yhteensä $20$ ympäristövahinkoa eikä yhtään säteilyvahinkoa.

Syöte

Syötteen ensimmäinen rivi sisältää neljä kokonaislukua $b$, $p$, $d$, ja $n$ välilyönneillä erotettuina: tukikohdan sijainti $b$, pulsarin purkauksien jaksonaika $p$, pulsarin jokaisen purkauksen aiheuttama lisävahinko $d$, suojapaikkojen määrä $n$. Seuraavat $n$ riviä sisältävät jokainen yhden kokonaisluvun, suojien sijainnit $a_1$, $\ldots $, $a_ n$, missä $0<a_1<\cdots <a_ n< b$.

Tuloste

Tulosta yksi kokonaisluku: pienin määrä vahinkoa, joka Tychon täytyy saada päästäkseen $b$:hen.

Rajoitukset ja pisteytys

Voit olettaa, että $p < b$ ja $n < b$. Kaikille syötteille pätee $1\leq b\leq 10^{12}$, $0\leq d \leq 10^6$, ja $0\leq n \leq 10^5$.

Ratkaisu testataan testiryhmillä, joista kullakin on oma pistemäärä. Jokainen testiryhmä sisältää joukon testitapauksia. Ryhmän pisteet saa vain, jos ratkaisee kaikki sen testitapaukset. Tehtävän lopullinen pistemäärä on suurin yksittäisen lähetyksen pistemäärä.

$^*$ Testiryhmässä $1$ Tycho voi joutua odottamaan kohdassa $0$ ennen kuin se on alkanut liikkua. Esimerkiksi esimerkkisyötteet $2$, $3$, ja $4$ kuuluvat testiryhmään $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