Problem F: Pet Adoption [Hard II]

## Problem F: Pet Adoption [Hard II]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1624  Solved: 361
[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 hash 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]