CF1534G A New Beginning

Annie 厌倦了在每场编程比赛中获胜并刷取无限积分。今天，她决定去种土豆。 Annie 的花园是一个无限的二维平面。她有 $n$ 个土豆要种，第 $i$ 个土豆必须种在 $(x_i, y_i)$。Annie 从点 $(0, 0)$ 出发，每走一步可以向右或向上移动一单位（即 $x$ 或 $y$ 坐标分别加 $1$）。在她行走的任意点 $(X, Y)$，她可以用土豆枪在任意位置种下土豆，在 $(x, y)$ 处种土豆需要消耗 $\max(|X-x|, |Y-y|)$ 单位的能量。请你计算种下所有土豆所需的最小总能量。 注意，Annie 可以在任意位置种下任意数量的土豆。

第一行包含一个整数 $n$（$1 \leq n \leq 800\,000$）。 接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$0 \leq x_i, y_i \leq 10^9$），表示第 $i$ 个土豆的位置。可能有多个土豆需要种在同一个位置。

输出种下所有土豆所需的最小总能量。

在样例 $1$ 中，Annie 可以直接走到每个位置种下土豆，能量消耗为 $0$。 在样例 $2$ 中，Annie 先走到 $(1, 0)$，用 $1$ 单位能量种下第二个土豆。接着，她走到 $(1, 1)$，用 $0$ 单位能量种下第一个土豆。 由 ChatGPT 4.1 翻译