Supercomputer

Time limit1sMemory limit128 MB

Summary

Given jobs with arrival times and required processor-time, schedule them with preemption on a single 100% processor to minimize the sum of completion-minus-arrival times.

Level: Hard8 of 10
Topics: Greedy, Sorting, Heap, Simulation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1
Input
```
3
0 6
20 8
15 10
```
Expected output
```
29
```
Example 2
Input
```
1
5 10
```
Expected output
```
10
```
Example 3
Input
```
3
0 3
0 1
0 2
```
Expected output
```
10
```