Problem H
Hilly Walk

UCLA is a campus that is full of hills, which makes walking incredibly tedious (as any UCLA student can tell you about). In fact, all of the hills in Los Angeles are in the shape of a parabola bounded by the $x$-axis, defined by the formula $y=-(x-a)^2+b$ for integers $a$ and $b$. However, something special happens if two or more hills overlap. They become a superhill at any $x$-value where at least two hills overlap, defined by the sum of all overlapping hills’ $y$ values (at each point of overlap). For example, if three hills exist at $x=4$ with heights $y_1$, $y_2$ and $y_3$, then the superhill at $x=4$ becomes $y_1+y_2+y_3$. UCLA’s campus only consists of these superhills, much to the chagrin of most students. You really want to complain to your friends about how annoying the walk at UCLA is, so you want to calculate the hilliness of the campus, which is the area bounded by these superhills and the $x$-axis. Can you calculate this hilliness value so you can complain to your friends?

Figure 1: Illustration of First Sample Case

For example, if you have two hills defined by the equations $y=-(x-3)^2 + 5$ and $y = -(x-4)^2 + 4$, as shown in the above figure, there will be a superhill between $x=2$ and $x = 3+\sqrt{5}$ as both hills overlap in this interval. The hilliness value would be the area of this superhill, i.e. the area of the green shaded region in the figure.

Input

The input starts with one line containing one integer $N$. This denotes the number of hills $1 \leq N \leq 100\, 000$.

$N$ lines follow containing two space-separated integers $a_ i$ and $b_ i$ ($0 \leq a_ i,b_ i \leq 1\, 000$) representing the hill $y = -(x-a_ i)^2+b_ i$.

Output

Output one line containing the hilliness value of UCLA. Your answer will be considered correct as long as it doesn’t exceed a relative or absolute error of $10^{-5}$.

2
3 5
4 4

21.768317

2
1 1
3 1

0