Адміністративна реформа#151

Адміністративна реформа

В Ужляндії вирішили провести адміністративно-територіальну реформу. Як відомо, в Ужляндії є міст, розташованих уздовж довгої прямої дороги, -е місто розташоване на відстані X_i (0 \leq X_1 < X_2 < \ldots < X_N \leq 10^9) кілометрів від початку дороги. В рамках реформи було прийнято рішення розділити Ужляндію на регіонів. Кожне місто має увійти рівно в один регіон.

У кожен регіон увійде від до міст, до того ж, ці міста повинні мати номери, що йдуть поспіль. Таким чином, кожен регіон характеризується числами та , для яких 1 \leq i, i + l - 1 \leq N, A \leq l \leq B і в регіон входять міста з номерами i, i + 1, \ldots, i + l - 1. Щоб мінімізувати витрати на обслуговування регіонів, адміністрація хоче, щоб максимальна відстань між містами, що входять в одну провінцію, було якомога менше. Допоможіть виконати поділ Ужляндії.

Вхідні дані

Перший рядок вхідного файлу містить чотири цілих числа: N, K, A, B (1 \leq N \leq 200, 1 \leq K \leq N, 1 \leq A \leq B \leq N, AK \leq N \leq BK). Другий рядок вхідного файлу містить цілих чисел: X_1, X_2, \ldots, X_N (0 \leq X_1 < X_2 < \ldots < X_N \leq 10^9).

Вихідні дані

Виведіть одне ціле число: мінімально можливе , таке щоб можна було розбити міста на регіони описаним чином, і відстань між містами всередині одного регіону не перевищувала .

Приклади

Приклад 1

Loading
Loading

Примітка

У прикладі оптимально перші 4 міста об'єднати в перший регіон, а п'яте і шосте — у другий. Максимальна відстань між двома містами в одному регіоні: 13 - 6 = 7.