Jump if you can!

One of the most popular games among the commando penguins is a game called jump if you can.

The rules are simple. Far away in Antarctica, at a secret penguin base, stand $n$ icebergs in a single line. Each iceberg is very tall and narrow, given by its distance $x_i$ from the reference point and its height $y_i$. A participant takes a rope of length $l$ and climbs to the top of the first iceberg. The goal is to reach the last iceberg by any means. With the rope, a penguin can jump from one iceberg to another if the distance between their tops is at most the rope length and the rope does not cross any iceberg between them (note that jumps can go from a lower iceberg to a higher one and from a higher one to a lower one). The winner is the boldest but most calculating penguin: the one who completes the task using the shortest rope.

Skipper decided to give himself and his team a short vacation, and of course to spend it at that same Antarctic base. The trip from Madagascar is long, so Kowalski, the smartest of the team, wants to prepare well for the upcoming contest. He wants to find in advance the minimum rope length needed to reach the last iceberg and win. Studying such things is not a common penguin pursuit, so he asked you for help.

The first line contains one integer $n$ ($2 \le n \le 100000$), the number of icebergs.

The second line contains $n$ pairs of integers $x_i, y_i$ ($0 \le x_i < x_{i+1} \le 10^9$, $0 \le y_i \le 10^9$), the coordinates of the iceberg tops.

Print one number, the minimum rope length needed to get from the first iceberg to the last one. The answer is accepted if its absolute or relative error does not exceed $10^{-6}$.