eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
3
1 5 10
0 1
Çıxış verilənləri #1
9
Giriş verilənləri #2
3
1 5 10
1 1
Çıxış verilənləri #2
27
Giriş verilənləri #3
3
1 5 2
0 1
Çıxış verilənləri #3
3
Giriş verilənləri #4
3
1 5 2
0 0
Çıxış verilənləri #4
7