#P2507. [SCOI2008] 配对

    ID: 1515 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp搜索期望各省省选2008四川

[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

3
3 65
45 10
60 25

32

3
5 5
6 7
8 8

5

提示

30%30 \% 的数据满足:n104n \le {10}^4
100%100 \% 的数据满足:1n1051 \le n \le {10}^5AiA_iBiB_i 均为 11109{10}^9 之间的整数。