Hamiltonian Circuit

시간 제한1초메모리 제한2048 MB

요약

n개의 쌍 (a_i, b_i)가 주어질 때, 간선 i에서 j의 가중치가 |a_i - b_j|인 완전 유향 그래프에서 해밀턴 회로의 최대 가중치 합을 구한다.

난이도: 어려움10점 중 8점
유형: 그리디, 정렬, 동적 계획법
정답자: 아직 제출이 없습니다

문제

You are given $n$ pairs of integers $(a\_i, b\_i)$ .

Consider a weighted directed complete graph $G$ with $n$ vertices, where the weight of the edge from $i$ ( $1 \leq i \leq n$ ) to $j$ ( $1 \leq j \leq n$ ) is $|a\_i - b\_j|$ .

Find a Hamiltonian circuit in $G$ such that the sum of weights of the edges it traverses is maximized, and output this maximum value.

입력

The first line of the input contains an integer $n$ ( $2 \leq n \leq 10^5$ ) representing the number of pairs.

Each of the next $n$ lines contains two integers $a\_i$ and $b\_i$ ( $0 \leq a\_i, b\_i \leq 10^9$ ) representing a single pair.

You may assume that all $2 n$ integers $a\_i$ and $b\_i$ are pairwise distinct.

출력

Print a line with a single integer: the maximum sum of weights of the Hamiltonian circuit.

힌트

In the example, consider the Hamiltonian circuit $1 \to 2 \to 3 \to 1$ , with edge weights $|1-2| + |8-5| + |4-10| = 10$ . It can be proven that there is no Hamiltonian circuit with sum of weights exceeding $10$ , so the answer is $10$ .

예제1

예제 1
입력
```
3
1 10
8 2
4 5
```
예상 출력
```
10
```