C1358 [SCOI2008]配对

内存限制:256 MB 时间限制:1000 ms

题目描述

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

输入格式

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

输出

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

样例

样例输入 1

3 3 65 45 10 60 25

样例输出 1

32

提示

$1 \le n \le 10^5$,$A_i$ 和 $B_i$ 均为 $1$ 到 $10^6$ 之间的整数。