Union

Time limit1sMemory limit256 MB

Summary

Given N origin-centered axis-aligned rectangles, each by its width and height, compute the area of their union.

Level: Medium7 of 10
Topics: Geometry, Sorting
Solved: No attempts yet

Problem

There are $N$ rectangles in the Cartesian plane. Every rectangle is centered at the origin, and its four sides are parallel to the coordinate axes. Each rectangle is therefore determined by its width (its length along the $x$ axis) and its height (its length along the $y$ axis). The figure below shows the first example.

Michuhol, a student in the design department, colored each rectangle and now wants to know the area of the colored part of the paper. In other words, find the area of the region that belongs to at least one rectangle (the union of all rectangles).

Input

The first line contains the number of rectangles $N$ ( $1 \le N \le 1\,000\,000$ ).

Each of the next $N$ lines contains the width $X$ and the height $Y$ of one rectangle. $X$ and $Y$ are even integers ( $2 \le X, Y \le 10^7$ ).

Output

Print the area of the colored region, that is, the area of the union of all rectangles, on a single line.

Examples2

Example 1
Input
```
3
8 2
4 4
2 6
```
Expected output
```
28
```
Example 2
Input
```
5
2 10
4 4
2 2
8 8
6 6
```
Expected output
```
68
```