← 返回题目列表

AtCoder · agc025_c

C. 间隔游戏

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

分数: 700 点

问题陈述

高桥和青木将玩一个带有数轴和一些线段的游戏。 高桥站在数轴上,他最初位于坐标处 0。 青木有 N 段。的 i-第段是 [L_i,R_i],即由坐标介于 L_i 和 R_i (含)。

游戏有 N 步骤。的 i第一步进行如下:

  • 首先,青木从 N 分割并告诉高桥。
  • 然后,高桥沿着数轴走到青木这次选择的线段内的某个点。 执行

之后 N 步骤,高桥将返回坐标 0 游戏结束。

让 K 是高桥在整场比赛中走过的总距离。青木将选择细分市场,以便 K 将尽可能大,高桥沿着线走,这样 K 将尽可能小。会有什么价值 K 到底?

约束

  • 1 ≤ N ≤ 10^5
  • -10^5 ≤ L_i < R_i ≤ 10^5
  • L_i 和 R_i 是整数。

输入

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

N
L_1 R_1
:
L_N R_N

输出

打印当 Takahashi 和 Aoki 执行上述操作时,Takahashi 在整个游戏中走过的总距离。 可以保证 K 始终是整数,当 L_i,R_i 是整数。


示例输入 1

3
-5 1
3 7
-4 -2

示例输出 1

10

高桥和青木的一种可能的行动顺序如下:

  • 青木选择第一段。高桥从坐标移动 0 to -4,覆盖距离 4.
  • 青木选择第三段。高桥留在坐标处 -4.
  • 青木选择第二段。高桥从坐标移动 -4 to 3,覆盖距离 7.
  • 高桥从坐标移动 3 to 0,覆盖距离 3.

这里高桥走过的距离是 14 (因为高桥没有以最佳方式移动)。 事实证明,如果两个玩家都以最佳方式移动,高桥走过的距离将为 10.


示例输入 2

3
1 2
3 4
5 6

示例输出 2

12

示例输入 3

5
-2 0
-2 0
7 8
9 10
-2 -1

示例输出 3

34