分数: 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