Secret Lines

Time limit1sMemory limit512 MB

Summary

Sum |Xa - Xb| * max(Va, Vb) over all pairs of members with given power and position.

Level: Medium7 of 10
Topics: Sorting, Divide and conquer, Prefix sum
Solved: No attempts yet

Problem

The members of a club are connected to each other by secret lines. There are N members, and each member has a nerd power V and a position X on a one dimensional axis. Laying one line needs a special material that withstands the nerd power of both endpoints. The number of units of material for the line between member a and member b is the distance between them multiplied by the larger of their two nerd powers.

$|X_a - X_b| \times \max(V_a, V_b)$

All of the members are on good terms, so every pair of two different members needs exactly one direct line. Compute the total number of units of material needed to lay all of the lines.

Input

The first line contains the number of members N ( $1 \le N \le 50000$ ).

Each of the next N lines contains one member's nerd power V and position X, separated by a space ( $0 \le V, X \le 50000$ ).

Output

Print the total number of units of material on one line. The total can exceed the range of a 32 bit integer.

Examples4

Example 1
Input
```
4
3 1
2 5
2 6
4 3
```
Expected output
```
57
```
Example 2
Input
```
1
50000 50000
```
Expected output
```
0
```
Example 3
Input
```
2
0 0
0 50000
```
Expected output
```
0
```
Example 4
Input
```
2
50000 0
50000 50000
```
Expected output
```
2500000000
```