Swap Space

You administer a large cluster of computers whose hard drives use several different file system types. You recently decided to unify them all on a single type. That is quite a challenge: every drive is in use, every drive is filled with important data up to its capacity, and you cannot afford to lose any of it. Reformatting a drive to the new file system may also change that drive's capacity by a lot. To make any reformat possible at all, you have to buy one extra hard drive, and you want to save money by keeping that extra storage as small as possible.

You can reformat the drives in any order. Before you reformat a drive, you must move all of its data to one or more other drives, splitting the data if necessary. Once a drive has been reformatted, you can immediately start using it to store data from other drives. Data does not have to return to the drive it started on. If some drives are smaller under the new file system, returning it is not even possible. Some data may also end up on the extra drive.

For example, suppose you have four drives A, B, C and D with capacities 6, 1, 3 and 3 gigabytes. Under the new file system the capacities become 6, 7, 5 and 5 gigabytes. If you buy only 1 gigabyte of extra space, you can move the data from drive B there and then reformat drive B. Drive B now has 7 gigabytes free, so you move the 6 gigabytes from drive A there and reformat drive A. Finally you move the six gigabytes held by drives C and D to drive A and reformat C and D.

The first line contains one integer $n$ ($1 \le n \le 10^6$), the number of drives in your cluster. Each of the following $n$ lines describes one drive with two integers $a$ and $b$, where $a$ is its capacity under the old file system and $b$ is its capacity under the new one.

All capacities are given in gigabytes and satisfy $1 \le a, b \le 10^9$. (One thousand petabytes should be enough for everyone, right?)

Print on one line the smallest total extra capacity in gigabytes you must buy to reformat every drive.