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

административная реформа
Имя входного файла: reform.in
Имя выходного файла: reform.out
Ограничение времени: 300 мс
Ограничение памяти: 256 M

В Ужляндии решили провести административно-территориальную реформу. Как известно, в Ужляндии есть N городов, расположенных вдоль длинной прямой дороги, и-е город расположен на расстоянии Xi (0 ≤ X1 <X2 <... <XN ≤ 109) километров от начала дороги.
В рамках реформы было прийгято решение разделить Ужляндию на К регионов. Каждый город должен войти ровно в один регион.
В каждый регион войдет от A до B городов, к тому же, эти города должны иметь номера, идущие подряд. Таким образом, каждый регион характеризуется числами i и l, для которых 1 ≤ i, i + l - 1 ≤ N, A ≤ l ≤ B и в регион входят города с номерами и, i + 1, ..., i + l - 1.
Чтобы минимизировать затраты на обслуживание регионов, администрация хочет, чтобы максимальное расстояние между городами, входящих в одну провинцию, было как можно меньше.
Помогите выполнить разделение Ужляндии.

Входные данные:
Первая строка входного файла содержит четыре целых числа: N, K, A, B (1 ≤ N ≤ 200, 1 ≤ K ≤ N, 1 ≤ A ≤ B ≤ N, AK ≤ N ≤ BK). Второй строка входного файла содержит N целых чисел: X1, X2, ..., XN (0 ≤ X1 <X2 <... <XN ≤ 109).

Исходные данные:
Выведите одно целое число: минимально возможное Z, такое чтобы можно было разбить город на регионы описанным образом, и расстояние между городами внутри одного региона не превышала Z.

Пояснения к примеру
В примере оптимально первые 4 города объединить в первый регион, а пятое и шестое - в другой. Максимальное расстояние между двумя городами в одном регионе: 13 - 6 = 7.
примеры
Входные данные в файле reform.in

6 2 2 4
1 2 3 4 6 13
Результат работы в файле reform.out

7

0