Description

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

Input

第一行为一个正整数n，接下来是n 行，每行两个整数Ai和Bi，保证所有 Ai各不相同，Bi也各不相同。

Output

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

Sample Input

3

3 65

45 10

60 25

Sample Output

32

HINT

1 <= n <= 10^5，Ai和Bi均为1到10^6之间的整数。

题解

首先将输入排序。

我们发现，在满足要求的情况下，不交叉的配对总比交叉配对优。

那么，我们观察$n=4$的情况。

可以发现，$a_4$不会与$b_1$配对，因为这样配对的最优策略是$a_1-b_2, a_2-b_3, a_3-b_4, a_4-b_1$，

那么有3种交换会使答案更优（如果它们满足条件）：

1. $a_1-b_1, a_4-b_2$

2. $a_2-b_1, a_4-b_3$

3. $a_3-b_1, a_4-b_4$

由于$b_1$只会和$a$中最多一个数相同，$a_4$同理，所以三种方案中必有一种合法。

将其推广，我们得到：

$a_i$不会和$b_j$配对，如果$i > j + 2$或$i < j - 2$。

那么就可以dp了（枚举后三个、后两个、后一个的配对方案）。

附代码：

#include 
     
      #include 
      
       #include 
       
        using std::min;typedef long long LL;LL INF = 1000000000000000LL;const int N = 100050;inline int readInt() {  int ans = 0;  char c;  do c = getchar(); while (!isdigit(c));  while (isdigit(c)) {    ans = ans * 10 + c - '0';    c = getchar();  }  return ans;}LL A[N], B[N];LL f[N];inline LL cost(int i, int j) {  if (A[i] == B[j]) return INF;  return std::abs(A[i] - B[j]);}int main() {  int n = readInt();  for (int i = 1; i <= n; ++i) {    A[i] = readInt();    B[i] = readInt();  }  if (n == 1 && A[1] == B[1]) return puts("-1"), 0;  std::sort(A + 1, A + n + 1);  std::sort(B + 1, B + n + 1);  f[0] = 0;  for (int i = 1; i <= n; ++i) {    f[i] = f[i - 1] + cost(i, i);    if (i > 1) f[i] = min(f[i], f[i - 2] + cost(i, i - 1) + cost(i - 1, i));    if (i > 2) {      f[i] = min(f[i], f[i - 3] + cost(i, i - 2) + cost(i - 1, i - 1) + cost(i - 2, i));      f[i] = min(f[i], f[i - 3] + cost(i, i - 2) + cost(i - 1, i) + cost(i - 2, i - 1));      f[i] = min(f[i], f[i - 3] + cost(i, i - 1) + cost(i - 2, i) + cost(i - 1, i - 2));    }  }  printf("%lld\n", f[n]);  return 0;}