Problem F: Pet Adoption [Hard II]

Problem F: Pet Adoption [Hard II]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2144  Solved: 488
[Submit][Status][Web Board]

Description

Lanran opened a pet adoption center. Each pet has a characteristic value \((0<p<2^{31})\) and each adopter also has a value \(q\) \((0<q<2^{31})\).

Lanran needs to provide the following services:

  • For a pet with characteristic value \(p\) arriving, it will be adopted by a person staying in the center whose \(q\) is the minimum closest to \(p\) or stay in the center if there is no adopter left.
  • For an adopter with value \(q\) arriving, he/she will choose a pet staying in the center whose \(p\) is the minimum closest to \(q\) or stay in the center if there is no pet left.

\(a\) is the minimum closest to \(v\) in set \(S\) if and only if:

  • for all \(a_x\in S\) there is \(|a-v|\le |a_x-v|\)
  • for all \(a_i\in S\) and \(|a-v|=|a_i-v|\) there is \(a\le a_i\)

the dissatisfaction for each adoption is defined as \(|p-q|\)

Input

The first line is a positive integer \(n\) (\(n\le 80000\)), which represents the total number of pets and adopters who come to the adoption center. The next n lines describe the pets and adopters who came to the adoption center in the order of arrival. Each line has two positive integers a, b, where a=0 for pets, a=1 for adopters, and b for character values.

Output

A positive integer representing the sum of the dissatisfaction of all adopted adopters of pets.

Sample Input

5                  
0 2                      
0 4                         
1 3
1 2
1 5

Sample Output

3

HINT

\(|3-2| + |2-4|=3\) and the last adopter has no pets to adopt.

[Submit][Status]