Жабки-стрибунці
Обмеження: 3 сек., 256 МіБ
Марічка та Зеник полюбляють романтичні вечори. Сьогодні вони вирішили милуватися жабками, що стрибають по камінцях.
Усього є \(n\) камінців, що розташовані на одній прямій та пронумеровані зліва направо від 1 до \(n\). Відстань між сусідніми камінцями становить один метр.
\(m\) жабок знаходяться на першому камінці (номер 1). За допомогою стрибків їм необхідно дістатись останнього камінця (номер \(n\)). Жабки можуть стрибати тільки праворуч (на камінець із більшим номером).
Мають виконуватися такі умови:
камінці \(a_1\), \(a_2\), …, \(a_k\) мають бути відвідані рівно однією жабкою;
на усі інші камінці (окрім першого та останнього) стрибати заборонено.
Якщо жабка номер \(i\) робить стрибок довший ніж \(d\) метрів, то вона витрачає на нього \(c_i\) одиниць енергії. Усі коротші стрибки не потребують жаб’ячої енергії.
Ваше завдання — знайти мінімальну кількість енергії, необхідну для того, аби усі жабки дістались останнього камінця.
Вхідні дані
У першому рядку задані чотири цілих числа \(n\), \(m\), \(k\) та \(d\).
У другому рядку задані \(m\) цілих чисел \(c_i\).
У наступному рядку задані \(k\) цілих чисел \(a_i\).
Вихідні дані
Мінімальна необхідна кількість енергії.
Обмеження
\(3 \le n \le 10^9\),
\(1 \le m, k \le 10^5\),
\(1 \le d, c_i \le 10^9\),
\(2 \le a_i < n\).
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 10 2 3 3 4 7 4 8 7 | 4 |
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 10 2 2 3 4 7 9 5 | 15 |
Надіслати розв'язок
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|