← 返回题目列表

AtCoder · joi2020_yo2_b

B. 草莓

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

配点: 100 点

問題文

佳石一护农场(以下简称JOI农场)是一座以东西狭长着称的草莓农场,其入口位于农场的最西端。下面,从入口向东 k 该点是您已行驶米数的点。 我们称之为 k 。

JOI农场内部 有 N 草莓。每个 它的编号为 1 到 N 。每个草莓都是时间 在 0 之前呈蓝色。草莓 i (1 \leqq i \leqq N) 是一个点 A_i 正在开花结果,时间到了 当它达到 T_i 时,它就会成熟并呈红色。

草莓在绿色时不能采收。换句话说,草莓 i 是时间 在 T_i 之前无法收获。你就是时间 指向 0 从 0 处的农场入口开始,每秒的最大速度为 1 在东西向移动(以米为单位)的同时收获草莓。假设收获草莓所需的时间可以忽略不计。

给定一个草莓农场的信息,编写一个程序来计算在收获所有红色状态的草莓后草莓返回入口所需的最短时间。

制約

  • 1 \leqq N \leqq 100\,000.
  • 0 \leqq A_i \leqq 1\,000\,000\,000 (=10^9) (1 \leqq i \leqq N).
  • 0 \leqq T_i \leqq 1\,000\,000\,000 (=10^9) (1 \leqq i \leqq N).
  • 所有输入值都是整数。

入力

输入是按以下格式从标准输入给出的。

N
A_1 T_1
A_2 T_2
\vdots
A_N T_N

出力

计算所有草莓在红色状态下采收后返回入口所需的最短时间。 在 1 行上输出。


入力例 1

10
1 3
2 1
3 4
4 1
5 5
6 9
7 2
8 6
9 5
10 3

出力例 1

20

开始 10 点(以秒为单位) 如果你移动到 10 ,你会沿途找到草莓。 2, 4, 5, 7, 8, 9, 10 可以按此顺序收获。之后 当你返回 10 点(以秒为单位) 如果你移动到 0 时,你会在路上发现草莓。 6, 3, 1 可以按此顺序收获。现在 您可以在所有 10 草莓仍呈红色时收获它们。


入力例 2

10
0 450
5 445
10 430
15 405
20 370
25 325
30 270
35 205
40 130
45 45

出力例 2

450

如果您按如下方式移动 450 你可以在几秒钟内收获所有红色状态的草莓。 移至

  1. 45 点(以秒为单位) 如果你移动到 45 。此时此刻 45 所以一护 你可以收获 10 。收获后 移至 45 点(以秒为单位) 如果你移动到 0 。
  2. 之后,40 点(以秒为单位) 如果你移动到 40 。此时此刻 130 所以一护 你可以收获 9 。收获后 移至 40 点(以秒为单位) 如果你移动到 0 。
  3. 之后,35 点(以秒为单位) 如果你移动到 35 。此时此刻 205 所以一护 你可以收获 8 。收获后 移至 35 点(以秒为单位) 如果你移动到 0 。
  4. 之后,30 点(以秒为单位) 如果你移动到 30 。此时此刻 270 所以一护 你可以收获 7 。收获后 移至 30 点(以秒为单位) 如果你移动到 0 。
  5. 之后,25 点(以秒为单位) 如果你移动到 25 。此时此刻 325 所以一护 你可以收获 6 。收获后 移至 25 点(以秒为单位) 如果你移动到 0 。
  6. 之后,20 点(以秒为单位) 如果你移动到 20 。此时此刻 370 所以一护 你可以收获 5 。收获后 移至 20 点(以秒为单位) 如果你移动到 0 。
  7. 之后,15 点(以秒为单位) 如果你移动到 15 。此时此刻 405 所以一护 你可以收获 4 。收获后 移至 15 点(以秒为单位) 如果你移动到 0 。
  8. 之后,10 点(以秒为单位) 如果你移动到 10 。此时此刻 430 所以一护 你可以收获 3 。收获后 移至 10 点(以秒为单位) 如果你移动到 0 。
  9. 之后,5 点(以秒为单位) 如果你移动到 5 。此时此刻 445 所以一护 你可以收获 2 。收获后 移至 5 点(以秒为单位) 如果你移动到 0 。
  10. 正是时候 已达到 450 从 0 ,所以 Ichigo 你可以收获 1 。在所有草莓收获的同时 到达 0 。

入力例 3

15
11 23
3 94
89 3
38 58
65 29
41 3
80 42
22 76
48 85
83 98
87 29
97 96
22 75
57 25
99 33

出力例 3

198