Fire Station Dilemma

A fire station on Ulleungdo has only one fire truck. At time 0, several fires break out at the same time. The truck can fight only one fire at a time, and it cannot move to another fire until the current one has been completely extinguished. Travel time is considered to be 0 seconds.

For each fire, arriving later never makes the extinguishing time shorter. If the truck arrives at a fire t seconds after it started, the time needed to extinguish that fire is a t + b seconds. The values a and b are nonnegative integers and may differ for each fire.

Choose the order of the fires so that the time needed to extinguish all fires is minimized, and output that minimum time.

The first line contains the number of fires n. n is a positive integer not greater than 200,000.

Each of the next n lines contains two integers a and b for one fire. Each of a and b is a nonnegative integer not greater than 40,000.

Print the minimum time needed to extinguish all fires, modulo 40,000.