Пожаротушащий робот
Пожаротушащий робот
Во время пожаров в Австралии, участок земли, на которой происходил пожар, был представлен как прямая, поделенная на 109
частей, пронумерованных от 1 до 109
. В данный момент на n частях участка происходит пожар. С целью тушения пожаров, был приглашен эксперт по лесным пожарам, Мурад.
Мурад собирается воспользоваться своим пожаротушащим роботом. У него есть p маленьких и q больших роботов. Все роботы работают согласно одной и той же системе. У системы есть диапазон пожара – всегда целое число. Если диапазон пожара равен w, то маленький робот может потушить w последовательных частей с места последней остановки, большой же робот 2w частей. Никакой робот не может в процессе тушения пожара двигаться или менять своё местоположение. Очевидно, что, чем больше диапазон пожара, тем больше электроэнергии тратят роботы. Поэтому Мурад хочет потушить пожар с минимально возможным диапазоном пожара. Помогите Мураду и вычислите минимально возможный диапазон пожара, при котором можно поутшить пожар.
Входные данные
В первой строке заданы три числа n (1 ≤ n ≤ 2000) , p и q (0 ≤ p,q ≤ 105
, p + q > 0) . В следующих n строках находится по одному числу xi
(1 ≤ xi
≤ 109
) - координаты горящих частей участка.
Выходные данные
Выведите минимально возможный диапазон пожара, при котором можно потушить пожар.
3 1 1 2 11 17
4
13 3 2 33 66 99 10 83 68 19 83 93 53 15 66 75
9