二维笛卡尔平面上有 n 个城市。两个城市之间的距离等于它们之间的曼哈顿距离(定义见注释)。城市的哈密顿循环被定义为所有 n 个城市的排列。该哈密顿环的长度定义为排列中相邻城市之间的距离加上排列中第一个和最后一个城市之间的距离之和。请计算给定城市的哈密顿循环的最长可能长度。
输入
第一行包含一个整数 n (3 ≤ n ≤ 105)。接下来是 n 行,每行由两个整数 xi 和 yi (0 ≤ xi, yi ≤ 109) 组成,表示城市的坐标。所有给定的点都是不同的。
输出
单线表示给定城市的哈密顿循环的最长可能长度。您不应该输出循环,而只输出其长度。
请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
4 1 1 1 2 2 1 2 2
输出 #1
6
注意
在该示例中,长度为 6 的可能哈密顿循环之一是 (1, 1) (1, 2) (2, 1) (2, 2)。不存在任何其他长度大于 6 的哈密顿环。
两个城市 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。