QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[+3]

# 7993. 哈密顿

Statistics

题目描述

给出 n 个二元组 (ai,bi)

考虑 n 个节点的带权有向完全图 G,其中从 i(1in)j(1jn) 的边边权为 |aibj|

G 的一条哈密顿回路使得其经过的边的边权和最大,并给出这个最大值。

输入格式

从标准输入读入数据。

输入的第一行一个整数 n(2n105) 表示二元组个数,接下来 n 行每行两个整数 ai,bi(0ai,bi109) 表示每个二元组。保证输入的 n 个二元组中的总共 2n 个数两两不同。

输出格式

输出到标准输出。

输出一行一个整数表示最大的哈密顿回路边权和。

样例

输入

3
1 10
8 2
4 5

输出

10

解释

考察哈密顿回路 1231,其边权和为 |12|+|85|+|410|=10。可以证明不存在哈密顿回路边权和超过 10,因此答案为 10