Problem C
Tycho

Космічний дослідницький корабель Tycho VIII повинен повернутися до бази після збору мінеральних зразків. Tycho рухається прямою лінією з позиції $0$ до дому на позицію $b$. Рухаючись, він продовжує свій шлях повільною, але сталою швидкістю $1$ одиниця на секунду. Кожну секунду Tycho отримує $1$ одиницю пошкоджень від важких планетарних умов.

Ситуацію ускладнює радіація від недалекої пульсари, яка додає $d$ додаткових одиниць пошкоджень кожні $p$ секунд. Однак радіаційних пошкоджень можна уникнути, шукаючи укриття в одному з $n$ різних місць для приховування—печерах, рослинностях, великих каменях, трупах мегафауни планети—під час подорожі. Tycho може вибрати будь-яку точку на маршруті та стояти на місці будь-яку цілу кількість секунд.

Початкова позиція $0$ та дім на $b$ обидва мають укриття, тому Tycho не отримує радіаційні пошкодження там.

Яке є мінімальне пошкодження, яке отримає Tycho під час повернення до дому?

Приклад

Розглянемо ситуацію, де дім знаходиться на позиції $18$, а укриття є на позиціях $8$ та $15$.

Припустимо, що період випромінювання пульсара дорівнює $4$, тому якщо Tycho не заховується в укритті, він отримуватиме пошкодження у моменти часу $4$, $8$, $12$ тощо. Якщо Tycho вирушає зі стартової позиції (де він прихований від радіації) у час $0$, то він може дістатися до першого укриття через $8$ секунд, отримавши випромінювання $d$ у час $4$ (але не отримуючи випромінювання в час $8$, оскільки тоді він захищений). Продовжуючи рух без зупинки, він дістається до бази в позиції $b$ в час $18$, зазнавши ще $d+d$ одиниць радіаційної шкоди (у часи $12$ та $16$ відповідно). Таким чином, він зазнає $d+d+d=3d$ одиниць радіаційної шкоди та $18$ одиниць шкоди від навколишнього середовища. Якщо ж Tycho зупиниться на другому укритті (у позиції $15$) на $1$ секунду, то у цей час удар пульсара у час $16$ не завдасть йому шкоди, і він дістанеться до бази в позиції $b$ в час $19$ із загальним дискомфортом $2d + 19$ одиниць. Це краще для більшості значень $d$. Обидві ситуації показані тут:

Якщо період пульсара дорівнює $10$, то Tycho може зачекати на початковій позиції протягом $2$ секунд, а потім просто повернутися додому, не зупиняючись в жодному укритті. Таким чином, він проходить перше укриття (на позиції $8$) саме в той момент, коли пульсар спалахує і прибуває до дому в час $20$, із загальним збитком від навколишнього середовища $20$ і жодної шкоди від радіації.

Вхідні дані

$0<a_1<\cdots <a_ n< b$. Перший рядок містить чотири цілих числа $b$, $p$, $d$ і $n$, розділені одинарним пробілом: розташування домашньої бази $b$, період спалахів пульсара $p$, додаткові радіаційні збитки $d$, спричинені кожним спалахом пульсара, кількість прихистків $n$. Наступні $n$ рядків містять ціле число, що вказує розташування прихистків $a_1$, $\ldots $, $a_ n$, де $0<a_1<\cdots <a_ n< b$.

Вихідні дані

Виведіть одне ціле число: мінімальну кількість пошкоджень, яку Tycho повинен зазнати, щоб досягти місця призначення $b$.

Обмеження та оцінювання

Ви можете припустити, що $p < b$ та $n < b$. Ми завжди маємо: $1\leq b\leq 10^{12}$, $0\leq d \leq 10^6$, та $0\leq n \leq 10^5$.

Ваше рішення буде перевірено на наборі тестових груп, кожна з яких має певну кількість балів. Кожна група містить певну кількість тестових випадків. Щоб отримати бали за групу тестів, потрібно вирішити всі тестові випадки в цій групі. Ваш кінцевий бал буде максимальним балом за одне відправлення.

$^*$ У групі тестів $1$ Tycho може все ще потрыбно чекати в позиції $0$ перед початком руху. Наприклад, вхідні дані для прикладів $2$, $3$, та $4$ належать до групи тестів $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