29147번 - Допрыгни, если сможешь! 스페셜 저지다국어

Одним из самых популярных развлечений у пингвинов-коммандос является игра <<Допрыгни, если сможешь!>>.

Суть игры заключается в следующем. Далеко в Антарктиде, на секретной базе пингвинов, есть удивительным образом стоящие в одну линию $n$ айсбергов. Каждый айсберг --- очень высокий и узкий, можно считать, что он задается расстоянием $x_i$ от точки отсчета и высотой $y_i$. Участник берет с собой веревку некоторой длины $l$ и забирается на верхушку первого айсберга. Его задача --- любым способом добраться до последнего айсберга. Используя веревку, пингвин может перепрыгнуть с одного айсберга на другой, если расстояние между верхушками данных айсбергов не больше, чем длина веревки, и веревка не пересекает ни один айсберг между ними (обратите внимание, что прыгать можно как с более низкого айсберга на более высокий, так и наоборот). Побеждает в игре самый смелый, но расчетливый: тот пингвин, который смог выполнить задание, используя самую короткую веревку.

Шкипер решил устроить себе и своей команде небольшой отпуск, и провести его, конечно, на той самой базе в Антарктиде. Дорога от Мадагаскара неблизкая, и Ковальски, как самый смышленный из команды, решил хорошо подготовиться к предстоящему состязанию. Он хочет заранее выяснить минимальную длину веревки, которая необходима для достижения последнего айсберга, и выиграть соревнование. Но изучение таких вещей --- дело не самое привычное для пингвина, поэтому он обратился за помощью к Вам.

В первой строке входного файла дано одно целое число $n$ ($2 \le n \le 100\,000$) --- количество айсбергов.

Во второй строке входного файла даны $n$ пар целых чисел $x_i, y_i$ ($0 \le x_i < x_{i+1} \le 10^9, 0 \le y_i \le 10^9$) --- координаты вершин айсбергов.

В единственной строке выходного файла выведите искомое число --- минимальную длину веревки, с помощью которой можно добраться от первого айсберга до последнего.

Ответ считается правильным, если его абсолютная или относительная погрешность не превосходит $10^{-6}$.