Byteotia is a beautiful, infinite, yet very flat and one-dimensional land, which can be identified with the number line. A meteor shower will soon fall on Byteotia. Thanks to the brilliant predictions of Byteotian meteorologists, it is known that exactly $n$ meteors will fall. Moreover, it is known exactly when and where each of them will fall: the $i$-th meteor will fall at time $t_i$ at point $x_i$.

It is currently time $0$, and Bytazar is at point $0$. Since meteors are dangerous, and Bytazar is very worried about the important data on his laptop, which he always carries with him, he would like to avoid a close encounter with any of them. More precisely, Bytazar would like to maximize his distance from the nearest falling meteor (each distance is measured at the moment the meteor falls).

We assume that Bytazar can run at a speed of at most one unit of distance per hour (to the right or left) and never gets tired. He can also turn around instantly (and multiple times).

Help Bytazar save himself and the data on his laptop. Write a program that reads information about the falling meteors and determines how far from the nearest meteor Bytazar can stay.

Input

The first line of the input contains a single integer $n$ ($1 \le n \le 200\,000$) specifying the number of falling meteors. The next $n$ lines contain the description of the meteors, one per line. The description of each meteor consists of two integers $t_i$ and $x_i$ ($0 \le t_i \le 10^9$, $-10^9 \le x_i \le 10^9$) specifying the time and position at which the $i$-th meteor will fall.

Output

Your program should output a single real number with a precision of one decimal place – the distance of Bytazar from the nearest falling meteor in the optimal solution.

If the result is an integer, it can be printed with one zero after the decimal point or without the decimal point.

Examples

Input 1

3
5 -3
7 6
4 -4

Output 1

5.5

Note

Bytazar can start running to the right at a speed of $\frac{1}{2}$, so that at time four he is at position $2$ (and is at a distance of $6$ units from the third meteor), and at time five he is at position $2\frac{1}{2}$ and is at a distance of $5\frac{1}{2}$ from the first meteor. At this moment, Bytazar should turn around and run to the left at the maximum speed of $1$, so that at time seven he is at position $\frac{1}{2}$ (at a distance of $5\frac{1}{2}$ from the second meteor).

In this way, Bytazar will maintain a distance of at least $5\frac{1}{2}$ from a falling meteor at all times; it is not possible to maintain a larger distance at all times.

Subtasks