Description

You are given $n$ integers $A_i$ and $n$ integers $B_i$. You need to pair them, that is, each $A_i$ is matched to exactly one $B_{p[i]}$. The goal is to minimize the sum of absolute differences over all pairs, but pairing two equal numbers is not allowed. For example, if $A = \{5, 6, 8\}$ and $B = \{5, 7, 8\}$, then an optimal pairing is $5 \sim 8$, $6 \sim 5$, $8 \sim 7$, with absolute differences $3, 1, 1$, summing to $5$. Note that $5 \sim 5$, $6 \sim 7$, $8 \sim 8$ are not allowed because equal numbers may not be paired.

Input Format

The first line contains a positive integer $n$. Then follow $n$ lines, each containing two integers $A_i$ and $B_i$. It is guaranteed that all $A_i$ are pairwise distinct, and all $B_i$ are also pairwise distinct.

Output Format

Output a single integer, the minimum possible sum of absolute differences of the paired integers. If it is impossible to pair, output -1.

3
3 65
45 10
60 25

32

3
5 5
6 7
8 8

5

Hint

Constraints:
$30 \%$ of the testdata satisfies: $n \le {10}^4$.
$100 \%$ of the testdata satisfies: $1 \le n \le {10}^5$, $A_i$ and $B_i$ are integers between $1$ and ${10}^9$.

Translated by ChatGPT 5