Жабки-стрибунці

Обмеження: 3 сек., 256 МіБ

Марічка та Зеник полюбляють романтичні вечори. Сьогодні вони вирішили милуватися жабками, що стрибають по камінцях.

Усього є \(n\) камінців, що розташовані на одній прямій та пронумеровані зліва направо від 1 до \(n\). Відстань між сусідніми камінцями становить один метр.

\(m\) жабок знаходяться на першому камінці (номер 1). За допомогою стрибків їм необхідно дістатись останнього камінця (номер \(n\)). Жабки можуть стрибати тільки праворуч (на камінець із більшим номером).

Мають виконуватися такі умови:

1. камінці \(a_1\), \(a_2\), …, \(a_k\) мають бути відвідані рівно однією жабкою;

2. на усі інші камінці (окрім першого та останнього) стрибати заборонено.

Якщо жабка номер \(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