← 返回题目列表

AtCoder · abc197_e

E. 旅行者

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 球,称为 Ball 1 通过 N,在数轴上。
球 i 位于坐标处 X_i.
每个球都有一个由整数 ID 表示的颜色 1 和 N (含);球颜色的ID i is C_i.
您现在位于坐标 0。您将以以下速度沿线移动来收集所有球 每秒 1 ,然后返回坐标 0.
在这里,您必须按照 ID 的非降序收集球。
收集球时,您必须位于该球的坐标处,但并不强制要求您在该坐标处收集球。
求从该坐标开始所需的最短时间 0,收集所有球,并返回坐标 0.

约束

  • 1 \le N \le 2 \times 10^5
  • |X_i| \le 10^9
  • X_i \neq X_j (i \neq j)
  • X_i \neq 0
  • 1 \le C_i \le N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
X_1 C_1
X_2 C_2
X_3 C_3
\hspace{15pt} \vdots
X_N C_N

输出

打印所需的秒数。


示例输入 1

5
2 2
3 1
1 3
4 2
5 3

示例输出 1

12

最优策略是:

  • 花费 3 秒到达坐标 3 并收集球 2;
  • 花费 1 第二次到达坐标 2 并收集球 1;
  • 花费 2 秒到达坐标 4 并收集球 4;
  • 花费 1 第二次到达坐标 5 并收集球 5;
  • 花费 4 秒到达坐标 1 并收集球 3;
  • 花费 1 第二次返回坐标 0.

在这里,我们按照 ID 的非降序收集球: 1, 2, 2, 3, 3.


示例输入 2

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

示例输出 2

38