[SCOI2008] 配对

题目描述

你有 $n$ 个整数 $A_i$ 和 $n$ 个整数 $B_i$。你需要把它们配对，即每个 $A_i$ 恰好对应一个 $B_{p[i]}$。要求所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配对。例如 $A = \{5, 6, 8\}$，$B = \{5, 7, 8 \}$，则最优配对方案是 $5 \sim 8$、$6 \sim 5$、$8 \sim 7$，配对整数的差的绝对值分别为 $3, 1, 1$，和为 $5$。注意，$5 \sim 5$、$6 \sim 7$、$8 \sim 8$ 是不允许的，因为相同的数不许配对。

输入格式

第一行为一个正整数 $n$，接下来是 $n$ 行，每行两个整数 $A_i$ 和 $B_i$，保证所有 $A_i$ 各不相同，$B_i$ 也各不相同。

输出格式

输出一个整数，即配对整数的差的绝对值之和的最小值。如果无法配对，输出 -1。

样例 #1

样例输入 #1

3
3 65
45 10
60 25

样例输出 #1

32

样例 #2

样例输入 #2

3
5 5
6 7
8 8

样例输出 #2

5

提示

$30 \%$ 的数据满足：$n \le {10}^4$； $100 \%$ 的数据满足：$1 \le n \le {10}^5$，$A_i$ 和 $B_i$ 均为 $1$ 到 ${10}^9$ 之间的整数。