qsgg and Move

题号：NC253368
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

平面直角坐标系上有 $n$ 个点，坐标给定，一开始你在原点，即 $(0,0)$ 。

每次移动，你会移动到离自己 曼哈顿距离 最远且之前没到达过的点

（如果有多个点最远，选择编号最小的点），移动距离即为曼哈顿距离。直到访问完最后一个点，移动结束。

你想知道移动的总距离。

注：在平面上，坐标 $(x_1,y_1)$ 的 $i$ 点与坐标 $(x_2,y_2)$ 的 $j$ 点的曼哈顿距离为： $d(i,j)=|x_1-x_2|+|y_1-y_2|.$

输入共 $n+1$ 行。

第一行一个整数表示 $n\ (1≤n≤10^6)$ 。

接下来 $n$ 行，每行 $2$ 个整数 $x_i,y_i \ (1≤x_i,y_i≤10^9)$ 表示编号为 $i$ 的坐标 $(x_i,y_i)$ 。

数据保证不同编号的坐标不相同。

输出一个整数，表示移动的总距离。

示例1

复制

复制

移动过程：移动过程如下：

移动距离分别为，和为  。