The cows are summering near the Front Range of the Rocky Mountains, not so far from Coach Rob's house. Visible on the horizon are $N$ mountains ($N \le 100{,}000$), for example (here, $N=5$):

                   /\
      /\          /  \  /\
     /  \/\    /\/    \/  \
    /    \ \  /  \    /    \
  -----------------------------

Each mountain is an isosceles triangle whose height is exactly twice the length of its base. A mountain is described by specifying the $x$-coordinate of each of the two endpoints of its base; these coordinates will be positive integers that fit nicely in a 16-bit signed entity. Your task is to compute the total area of the union of these mountains.

Input

• Line 1: A single integer, $N$
• Lines $2..N+1$: Each line describes a single mountain with two sorted space-separated integers.

Output

A single integer, giving the area of the union of the mountains. This area will always be an integer and will always fit into 32 signed bits.

Examples

Input 1

5
2 7
6 9
12 15
14 21
20 25

Output 1

114

Problem credits: Brian Dean, 2001