题目描述
给出 n 个二元组 (ai,bi)。
考虑 n 个节点的带权有向完全图 G,其中从 i(1≤i≤n) 到 j(1≤j≤n) 的边边权为 |ai−bj|。
求 G 的一条哈密顿回路使得其经过的边的边权和最大,并给出这个最大值。
输入格式
从标准输入读入数据。
输入的第一行一个整数 n(2≤n≤105) 表示二元组个数,接下来 n 行每行两个整数 ai,bi(0≤ai,bi≤109) 表示每个二元组。保证输入的 n 个二元组中的总共 2n 个数两两不同。
输出格式
输出到标准输出。
输出一行一个整数表示最大的哈密顿回路边权和。
样例
输入
3
1 10
8 2
4 5
输出
10
解释
考察哈密顿回路 1→2→3→1,其边权和为 |1−2|+|8−5|+|4−10|=10。可以证明不存在哈密顿回路边权和超过 10,因此答案为 10。