Problem Description

You have $n$ integers $A_i$ and $n$ integers $B_i$. You need to pair them, meaning each $A_i$ must correspond to exactly one $B_{p[i]}$. The goal is to minimize the sum of the absolute differences of all paired integers, with the condition that no two identical numbers can be paired. For example, given $A = \{5, 6, 8\}$ and $B = \{5, 7, 8\}$, the optimal pairing scheme is $5 \sim 8$, $6 \sim 5$, $8 \sim 7$, with the absolute differences being $3, 1, 1$, summing up to $5$. Note that pairings like $5 \sim 5$, $6 \sim 7$, $8 \sim 8$ are not allowed because identical numbers cannot be paired.

Input Format

The first line contains a positive integer $n$. The following $n$ lines each contain two integers $A_i$ and $B_i$, ensuring that all $A_i$ are distinct and all $B_i$ are distinct.

Output Format

Output a single integer, which is the minimum sum of the absolute differences of the paired integers. If no valid pairing is possible, output -1.

Sample Input and Output

Sample Input #1

3
3 65
45 10
60 25

Sample Output #1

32

Sample Input #2

3
5 5
6 7
8 8

Sample Output #2

5

Notes/Hints

$30\%$ of the test cases satisfy: $n \le 10^4$;
$100\%$ of the test cases satisfy: $1 \le n \le 10^5$, and $A_i$ and $B_i$ are integers between $1$ and $10^9$.

见题面 Input 部分

见题面 Output 部分