#P2507. [SCOI2008] 配对
[SCOI2008] 配对
题目描述
你有 个整数 和 个整数 。你需要把它们配对,即每个 恰好对应一个 。要求所有配对的整数差的绝对值之和尽量小,但不允许两个相同的数配对。例如 ,,则最优配对方案是 、、,配对整数的差的绝对值分别为 ,和为 。注意,、、 是不允许的,因为相同的数不许配对。
输入格式
第一行为一个正整数 ,接下来是 行,每行两个整数 和 ,保证所有 各不相同, 也各不相同。
输出格式
输出一个整数,即配对整数的差的绝对值之和的最小值。如果无法配对,输出 -1
。
3
3 65
45 10
60 25
32
3
5 5
6 7
8 8
5
提示
的数据满足:;
的数据满足:, 和 均为 到 之间的整数。