Sails

A new pirate sailing ship is being built. The ship has $N$ masts (vertical poles), each divided into unit-sized segments; the height of a mast equals its number of segments. Each mast carries a number of sails, and every sail fits exactly into one segment. The sails on a single mast may be placed arbitrarily among its segments, but each segment can hold at most one sail.

Different arrangements of sails generate different amounts of thrust in the wind. A sail placed in front of other sails at the same height catches less wind and contributes less thrust. For each sail we define its inefficiency as the number of sails that are at the same height and behind it. Here "in front of" and "behind" refer to the orientation of the ship: in the figure below, "in front of" means to the left and "behind" means to the right.

The total inefficiency of an arrangement is the sum of the inefficiencies of all individual sails.

The ship in the figure has 6 masts, whose heights from front (left) to back (right) are 3, 5, 4, 2, 4, and 3. The arrangement shown has a total inefficiency of 10; the number written inside each sail is that sail's inefficiency.

Given the height and the number of sails on each of the $N$ masts, write a program that determines the smallest possible total inefficiency.

The first line contains an integer $N$ ($2 \le N \le 100\,000$), the number of masts.

Each of the next $N$ lines contains two integers $H$ and $K$ ($1 \le H \le 100\,000$, $1 \le K \le H$): the height of a mast and the number of sails on it. The masts are listed in order from the front of the ship to the back.

Print a single integer: the smallest possible total inefficiency.

The result can exceed the range of a 32-bit integer, so use a 64-bit integer type (for example, long long in C/C++) to compute and print it.