#3270. [SCOI2008] 配对

[SCOI2008] 配对

[SCOI2008] 配对

题目描述

你有 nn 个整数 AiA_inn 个整数 BiB_i。你需要把它们配对,即每个 AiA_i 恰好对应一个 Bp[i]B_{p[i]}。要求所有配对的整数差的绝对值之和尽量小,但不允许两个相同的数配对。例如 A={5,6,8}A = \{5, 6, 8\}B={5,7,8}B = \{5, 7, 8 \},则最优配对方案是 585 \sim 8656 \sim 5878 \sim 7,配对整数的差的绝对值分别为 3,1,13, 1, 1,和为 55。注意,555 \sim 5676 \sim 7888 \sim 8 是不允许的,因为相同的数不许配对。

输入格式

第一行为一个正整数 nn,接下来是 nn 行,每行两个整数 AiA_iBiB_i,保证所有 AiA_i 各不相同,BiB_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%30 \% 的数据满足:n104n \le {10}^4100%100 \% 的数据满足:1n1051 \le n \le {10}^5AiA_iBiB_i 均为 11109{10}^9 之间的整数。