Кінець

Обмеження: 2 сек., 256 МіБ

Знаєте, після олімпіади відбувається багато всяких дивних речей. Наприклад, вас можуть заставити танцювати з вазоном.

Уявіть собі, що у вас є коридор довжиною \(l\), у якому є колони радіусом \(r\). І вам потрібно пронести якомога більший вазон з одного кінця коридора в інший його кінець.

Узагальнимо. Ви обираєте собі вазон, входите в коридор. Правий його край має координату \(x_r\), а лівий — \(x_l\). Сторони коридора є паралельними осі \(OY\). У коридорі стоять \(n\) колон радіусом \(r\) із центрами в певних місцях.

Вам потрібно дізнатися, який максимальний радіус вазона можна обрати, щоб пройти коридор із вазоном у руках. Можна вважати, що вазон ну дууже великий, тож вам нема змісту тримати його не горизонально.

У вас є всі потрібні дані.

Допоможіть же собі, напишіть для цього програму.

Вхідні дані

Перший рядок містить два цілі числа \(x_l\) та \(x_r\) — координати лівої та правої стін коридору.

У другому записане ціле число \(r\) — радіус колон у коридорі.

У третьому рядку записане ціле число \(n\) — кількість колон.

У кожному наступному рядку записані два цілі числа \(x_i\) та \(y_i\) — координати центру \(i\)-тої колони.

Колони можуть виходити за межі коридору та накладатися.

Вихідні дані

У єдиному рядку виведіть дійсне число — максимальний діаметр вазона. Гарантується, що відповідь існує. Відповідь вважатиметься правильною, якщо її абсолютна чи відносна похибка не перевищує \(10^{-4}\).

Обмеження

\(|x_i|, |y_i| \le 10^6\),

20% тестів:

\(1 \le r \le 10^3, n \le 50\),

80% тестів:

\(1 \le r \le 10^6, n \le 200\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
0 90 3 4 10 10 70 10 50 50 10 90	47.000