e-olymp
Задачи

Супер платформи

Супер платформи

У багатьох старих іграх з двовимірною графікою можна зіткнутися з такою ситуацією. Який-небудь герой стрибає по платформам (або острівкам), які висять у повітрі. Він повинен перебратись від одного краю екрану до іншого. При цьому, при стрибку з однієї платформи на сусідню, у героя витрачається |y2–y1| енергії, де y2 та y1 – висоти, на яких розміщені ці платформи. Крім того у героя є суперприйом, який дозволяє перестрибнути через платформу, причому на це витрачається 3·|y2–y1| одиниць енергії. Кількість використань суперприйому обмежена й повинна перебувати в межах від kmin до kmax разів (обидві межі включно). Звичайно ж, енергію потрібно витрачати максимально економно.

Припустимо, що вам відомі координати усіх платформ у порядку від лівого краю до правого та обмеження на кількість використань суперприйому kmin та kmax. Чи зможете ви знайти, яку мінімальну кількість енергії потрібно герою, щоб дістатись від першої платформи до останньої?

Вхідні дані

У першому рядку записана кількість платформ n (1 ≤ n ≤ 10000). Другий рядок містить n натуральних чисел, які не перевищують 30000 – висоти, на яких розміщено платформи. Третій рядок містить два цілі невід’ємні числа kmin та kmax(0 ≤ kmin ≤ kmax ≤ (n–1)/2).

Вихідні дані

Виведіть єдине число – мінімальну кількість енергії, яку повинен витратити гравець на подолання платформ (звісно ж у припущенні, що cheat-коди використовувати не можна).

Лимит времени 1 секунда
Лимит использования памяти 256 MiB
Входные данные #1
3
1 5 10
0 1
Выходные данные #1
9
Входные данные #2
3
1 5 10
1 1
Выходные данные #2
27
Входные данные #3
3
1 5 2
0 1
Выходные данные #3
3
Входные данные #4
3
1 5 2
0 0
Выходные данные #4
7
Непредставиме число