Cow Gathering

Problem Source

Original problem: USACO04OPEN MooFest G.

Although an $O(N^2)$ simulation can pass, a divide and conquer or Fenwick tree approach is recommended for the full challenge.

Related (harder) problem where $O(N^2)$ fails: P5094.

Problem Description

John's $n$ cows attend the "Moo Moo Gathering" every year. It is a grand event in the cow world, with many activities such as stacking hay, jumping fences, and patting cowboys on the butt.

When they gather, the $i$-th cow stands at coordinate $x_i$, and no two cows share the same coordinate.

The cows are very loud. When cow $i$ and cow $j$ communicate, they produce a volume of

where $v_i$ and $v_j$ are the hearing abilities of cow $i$ and cow $j$ respectively.

Assuming every pair of cows is talking simultaneously, compute the sum of the volumes produced by all cows.

Input Format

The first line contains a single integer $n$, $1 \le n \le 3 \times 10^4$.

Lines $2$ through $n + 1$: the $(i + 1)$-th line contains two integers $v_i$ and $x_i$ ($1 \le v_i, x_i \le 3 \times 10^4$).

Output Format

Output a single integer: the total volume produced by all cows.

Sample Input

4
3 1
2 5
2 6
4 3

Sample Output

57