Hide

Problem C
Tycho

Languages da de en fi lt lv pl uk
/problems/boi23.tycho/file/statement/uk/img-0001.jpg

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

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

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

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

Приклад

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

\includegraphics[width=.3\textwidth ]{img/samplesetup}

Припустимо, що період випромінювання пульсара дорівнює $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$. Обидві ситуації показані тут:

\includegraphics[width=.8\textwidth ]{img/sample1_2.pdf}

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

\includegraphics[width=.4\textwidth ]{img/sample3.pdf}

Вхідні дані

$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$

$8$

$p\leq 10^6$ та Tycho не повинен чекати після виходу з позиції $0$.$^*$

$2$

$5$

$b\leq 1000$, $p\leq 100$, $n\leq 10$

$3$

$7$

$b\leq 1000$

$4$

$15$

$p\leq 10^6$, $n\leq 1000$

$5$

$20$

$p\leq 100$

$6$

$35$

$p\leq 10^6$

$7$

$10$

Без додаткових обмежень

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

Sample Input 1 Sample Output 1
18 4 5 2
8
15
29
Sample Input 2 Sample Output 2
18 4 0 2
8
15
18
Sample Input 3 Sample Output 3
18 10 100 2
8
15
20
Sample Input 4 Sample Output 4
18 4 100 0
418
Sample Input 5 Sample Output 5
65 20 100 3
14
25
33
172