Пожежогасильний робот
Під час пожеж в Австралії, ділянка землі, де відбувається пожежа, представлена у вигляді прямої, поділеної на 10^9 частин, пронумерованих від 1 до 10^9. Наразі пожежа охопила n частин цієї ділянки. Для боротьби з вогнем був запрошений експерт з лісових пожеж, Мурад.
Мурад планує використати своїх пожежогасильних роботів. У нього є p маленьких і q великих роботів. Усі роботи працюють за однаковою системою. У системи є параметр — діапазон пожежі, який завжди є цілим числом. Якщо діапазон пожежі дорівнює w, то маленький робот може загасити w послідовних частин, починаючи з місця останньої зупинки, а великий робот — 2w частин. Жоден робот не може переміщатися або змінювати своє місцезнаходження під час гасіння пожежі. Очевидно, що чим більший діапазон пожежі, тим більше електроенергії витрачають роботи. Тому Мурад прагне загасити пожежу з мінімально можливим діапазоном пожежі. Допоможіть Мураду визначити мінімально можливий діапазон пожежі, при якому можна загасити пожежу.
Вхідні дані
У першому рядку задано три числа: n (1 ≤ n ≤ 2000), p і q (0 ≤ p, q ≤ 10^5, p + q > 0). У наступних n рядках знаходиться по одному числу x[i] (1 ≤ x[i] ≤ 10^9) — координати палаючих частин ділянки.
Вихідні дані
Виведіть мінімально можливий діапазон пожежі, при якому можна загасити пожежу.