Supercomputer

The company BajtoLicz owns a very fast server, BL87. To make use of its power, the company decided to launch a service that runs, on the server, programs submitted by its clients. Each submitted program needs a certain amount of computing power (processor time) in order to run.

A program's execution time is counted from the moment the company receives the program until the moment its execution finishes. In other words, one program's execution time equals (finish time) $-$ (arrival time).

The BL87 server can run any number of programs in parallel, and each running program is assigned a certain percentage of the processor's power (determined by its priority). The total processor power is fixed at 100%, so at any instant the shares assigned to the running programs sum to at most 100%. It is also allowed to pause a program and later resume it, according to different priorities (preemption).

For a given list of jobs, write a program that finds the minimum possible sum of the execution times of all jobs.

Your program should:

• read the number of programs to run on the server and the description of each program,
• compute the minimum sum of the execution times of all jobs,
• print the result.

The first line contains an integer $n$ ($1 \le n \le 100000$), the number of programs to run. Each of the next $n$ lines contains two integers $a$ and $b$ ($0 \le a, b \le 10^9$), the arrival time of a program and the processor time needed to run it, respectively.

Print a single integer $k$, the minimum sum of the execution times of all programs.