Minimum Extra Storage for Unified File System

You are given a collection of hard drives, each filled to capacity with important data, and you need to reformat them so that they all use the same new file system. Reformating a drive changes its capacity. To reformat a drive, its entire data (which exactly equals its old capacity) must be moved to other drives (or the extra temporary drive you buy), possibly splitting the data among them. After reformatting a drive, its capacity becomes the new capacity, and it immediately can be used to store data from other drives. Note that in the final allocation, the data does not have to reside on the same drives as before. Your task is to determine the minimum extra storage you must purchase so that by choosing a suitable reformatting order, the reformatting process can be completed without data loss.

The input consists of n drives. For each drive, you are given two integers: the current capacity (which equals the amount of data on the drive) and the capacity after reformatting under the new file system. You may reformat the drives in any order, but before reformatting any drive you must move its data to other drives (or the extra drive). Data can be split arbitrarily. You need to compute the minimum size of the extra drive required to accomplish this safely.

Note: It is always possible to reformat the drives if you purchase sufficient extra storage.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of drives. Each of the next n lines contains two space‐separated integers a and b (1 ≤ a, b ≤ 10⁹), where a is the current capacity (amount of data) of a drive and b is its capacity after reformatting.

outputFormat

Output a single integer—the minimum extra storage required (in the same units as the drive capacities) to be able to reformat all drives without loss of data.

sample

4
6 6
1 7
3 5
3 5

1