27266번 - Реформы в королевстве 다국어

В одном королевстве есть $n$ городов, расположенных вдоль длинной прямой дороги, $i$-й город расположен на расстоянии $x_i$ километров от начала дороги ($0 \le x_1 < x_2 < \ldots < x_n \le 10^9$).

В ближайшее время король планирует провести реформу управления королевством и разделить его на $k$ провинций. Каждый город должен войти ровно в одну провинцию.

В каждую провинцию войдет от $a$ до $b$ городов, причем эти города должны иметь следующие подряд номера. Таким образом, каждая провинция характеризуется числами $i$ и $l$, для которых $1 \le i$, $i + l - 1 \le n$, $a \le l \le b$ и в провинцию входят города с номерами $i, i + 1, \ldots, i + l - 1$.

Чтобы минимизировать затраты на обслуживание провинций, король хочет, чтобы максимальное расстояние между городами, входящими в одну провинцию, было как можно меньше. Помогите королю выполнить разделение королевства.

Первая строка ввода содержит четыре целых числа: $n$, $k$, $a$ и $b$ ($1 \le n \le 200$, $1 \le k \le n$, $1 \le a \le b \le n$, $ak \le n \le bk$). Вторая строка ввода содержит $n$ целых чисел: $x_1, x_2, \ldots, x_n$ ($0 \le x_1 < x_2 < \ldots < x_n \le 10^9$).

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

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