AT_abc197_e [ABC197E] Traveler

题目描述

在数轴上有 $N$ 个球，从球 $1$ 到球 $N$。
球 $i$ 位于坐标 $X_i$。
每个球都有一个用 $1$ 到 $N$ 之间的整数表示的颜色，球 $i$ 的颜色用整数 $C_i$ 表示。
现在你位于坐标 $0$，你可以以每秒 $1$ 的速度在数轴上移动，要求你收集所有的球并回到坐标 $0$。
在这个过程中，将球的颜色按照收集顺序排列时，必须是广义单调递增的。
要收集一个球，你必须到达与球相同的坐标，但你可以选择在能够收集球的时候不收集它。
请你求出，从坐标 $0$ 出发，收集所有球并回到坐标 $0$ 所需的最小时间。

输入格式

输入以如下格式从标准输入读入。

$N$
$X_1$ $C_1$
$X_2$ $C_2$
$X_3$ $C_3$
$\vdots$
$X_N$ $C_N$

输出格式

输出答案（单位为秒）。

输入输出样例 #1

输入 #1

5
2 2
3 1
1 3
4 2
5 3

输出 #1

12

输入输出样例 #2

输入 #2

9
5 5
-4 4
4 3
6 3
-5 5
-3 2
2 2
3 3
1 4

输出 #2

38

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $|X_i| \leq 10^9$
• $X_i \neq X_j\ (i \neq j)$
• $X_i \neq 0$
• $1 \leq C_i \leq N$
• 输入中的所有值均为整数

样例解释 1

最优的行动方式如下：

• 用 $3$ 秒移动到坐标 $3$，收集球 $2$
• 用 $1$ 秒移动到坐标 $2$，收集球 $1$
• 用 $2$ 秒移动到坐标 $4$，收集球 $4$
• 用 $1$ 秒移动到坐标 $5$，收集球 $5$
• 用 $4$ 秒移动到坐标 $1$，收集球 $3$
• 用 $1$ 秒回到坐标 $0$
  将球的颜色按照收集顺序排列为 $1, 2, 2, 3, 3$，是广义单调递增的。

由 ChatGPT 4.1 翻译