Paper Rolls

Interview

Time limit1sMemory limit128 MB

Summary

Set every roll to one shared unrolled length within each total length using the fewest 1-cm moves.

Level: Medium5 of 10
Topics: Sorting, Math
Solved: No attempts yet

Problem

There are $n$ toilet paper rolls in a bathroom. The $i$ -th roll has a total length $d_i$ and a currently unrolled length $r_i$ , and the unrolled length can never exceed the total length (that is, $0 \le r_i \le d_i$ ).

In one move you may roll up or unroll exactly 1 cm of any single roll; in other words, one move increases or decreases some $r_i$ by $1$ , and $0 \le r_i \le d_i$ must still hold afterwards. Determine the minimum number of moves needed to make every roll have the same unrolled length.

Input

The first line contains the number of rolls $n$ ( $1 \le n \le 10^6$ ). Each of the next $n$ lines describes one roll with two integers $d_i$ and $r_i$ , the total length and the unrolled length of the $i$ -th roll ( $0 \le r_i \le d_i \le 10^9$ ).

Output

Print a single integer: the minimum number of moves needed to make the unrolled lengths of all rolls equal.

Examples2

Example 1
Input
```
3
50 10
40 20
30 30
```
Expected output
```
20
```
Example 2
Input
```
1
10 5
```
Expected output
```
0
```