题目描述
你有 n 个整数 Ai 和 n 个整数 Bi。你需要把它们配对,即每个 Ai 恰好对应一个 Bp[i]。要求所有配对的整数差的绝对值之和尽量小,但不允许两个相同的数配对。例如 A={5,6,8},B={5,7,8},则最优配对方案是 5∼8、6∼5、8∼7,配对整数的差的绝对值分别为 3,1,1,和为 5。注意,5∼5、6∼7、8∼8 是不允许的,因为相同的数不许配对。
输入格式
第一行为一个正整数 n,接下来是 n 行,每行两个整数 Ai 和 Bi,保证所有 Ai 各不相同,Bi 也各不相同。
输出格式
输出一个整数,即配对整数的差的绝对值之和的最小值。如果无法配对,输出 -1
。
提示
30% 的数据满足:n≤104;
100% 的数据满足:1≤n≤105,Ai 和 Bi 均为 1 到 109 之间的整数。