해밀턴 회로

정수 쌍 $(a_i, b_i)$가 $n$개 주어진다.

정점이 $n$개인 가중 방향 완전 그래프 $G$를 생각하자. 정점 $i$ ($1 \leq i \leq n$)에서 정점 $j$ ($1 \leq j \leq n$)로 가는 간선의 가중치는 $|a_i - b_j|$이다.

$G$의 해밀턴 회로 중 간선 가중치의 합이 최대인 회로를 찾고, 그 최댓값을 출력하라.

첫 줄에 쌍의 개수 $n$ ($2 \leq n \leq 10^5$)이 주어진다.

이어서 $n$개의 줄에 정수 $a_i$와 $b_i$ ($0 \leq a_i, b_i \leq 10^9$)가 한 줄에 하나씩 주어진다.

모든 $2n$개의 정수 $a_i$와 $b_i$는 서로 모두 다르다고 가정해도 된다.

해밀턴 회로의 가중치 합의 최댓값을 한 줄에 정수 하나로 출력한다.

예제에 나온 회로 $1 \to 2 \to 3 \to 1$을 보자. 간선 가중치는 $|1-2| + |8-5| + |4-10| = 10$이다. 가중치 합이 10을 넘는 해밀턴 회로는 없으므로 답은 10이다.