Sails#282
A new pirate sailing ship is being built. The ship has masts, each divided into unit segments. The height of a mast is equal to the number of its segments. Each mast is fitted with a certain number of sails, and each sail occupies exactly one segment. Sails on a mast can be placed on any segment, but each segment can hold at most one sail.
Different configurations of sails generate different thrusts when exposed to wind. A sail that is in front of another sail at the same height receives less wind and generates less thrust. For each sail, its inefficiency is defined as the total number of sails that are behind this sail at the same height. Note that "in front of" and "behind" are given relative to the direction of the ship: in the figure, "in front of" is to the left and "behind" is to the right.
The total inefficiency of a configuration is the sum of the inefficiencies for all sails.
Write a program that, given the height and number of sails on each of the masts, determines the smallest possible total inefficiency.
The first line contains an integer (2 \le N \le 100\ 000), the number of masts on the ship.
Each of the next lines contains two integers and (1 \le H \le 100\ 000, 1 \le K \le H): the height of the mast and the number of sails on it. Masts are listed from the front to the back of the ship.
Output a single integer — the minimal possible total inefficiency.
Example 1