P4647 [IOI 2007] sails Sails

Let us build a new pirate ship. There are $N$ masts on the ship. Each mast is divided into unit-length sections. The length of a mast equals the number of sections it is divided into. Some sails are hung on each mast, and each sail occupies exactly one section of the mast. On a single mast, the sails can be arranged arbitrarily among different sections, but each section can have at most one sail. In the wind, different arrangements of sails produce different propulsive forces. A sail closer to the bow produces less propulsive force than a sail behind it at the same height. In other words, the propulsive force of a sail closer to the bow is discounted because of the sails behind it at the same height. For any sail, its propulsive force discount equals the number of sails that are behind it and at the same height. The total propulsive force discount of an arrangement equals the sum of the propulsive force discounts of all sails under that arrangement.  This ship has 6 masts. From front (left in the figure) to back, their heights are 3, 5, 4, 2, 4, and 3. The total propulsive force discount of the sail arrangement shown in the figure is 10. The figure also gives the propulsive force discount of each individual sail. Given the heights of the $N$ masts and the number of sails hung on each mast, write a program to find the minimum possible total propulsive force discount among all arrangements.

The first line contains an integer $N(2 \leq N \leq 100 000)$, the number of masts. The next $N$ lines each contain two integers $H$ and $K(1 \leq H \leq 100 000, 1 \leq K \leq H)$, representing the height of the corresponding mast and the number of sails on it. The masts are given in order from the bow to the stern.

Output one integer, the minimum total propulsive force discount that can be achieved. Note: Use a 64-bit integer type when computing and outputting the result (```long long``` in C/C++, ```int64``` in Pascal).

This sample testdata is the same as the sample shown in the figure on the previous page. In the testdata worth 25 points, the total number of different sail arrangements does not exceed $1,000,000$ . Translated by ChatGPT 5