UOJ Logo

NOI.AC

1S 512MB
统计

Problem Statement

一天早上,有 $n$ 个人来到一个无限高的大厦上班。其中第 $i$ 个人在 $t_i$ 时刻来到大厅,想要去第 $x_i$ 层。没有两个人会同时来到大厅。

每个人来到大厅(即第 $0$ 层)后,只要电梯一来便会进入电梯。第 $0$ 时刻电梯在大厅。因为没有人愿意在电梯里来到大厅第二次,所以每次来到大厅时,电梯都必须是空的。

你要控制电梯的升降操作。电梯上(或下)一层所需要的时间为 $1$ 单位时间,而开关门、停靠、上下电梯等时间均可忽略不计。试求出电梯运送完所有人并回到大厅所要的最小时间。

Input Format

第一行一个正整数 $n$,表示人数。

接下来 $n$ 行,每行两个正整数 $t_i,x_i$,描述每个人的信息。

Output Format

输出一行一个数,表示所需要的最小时间。

Sample Input

3
1 9
2 6
15 6

Sample Output

31

Sample Explanation

操作序列为:在第 $1$ 单位时间末,操控电梯向上走到 $9$ 层再回来。此时为第 $19$ 单位时间,后两人进入电梯。然后操控电梯走到第 $6$ 层再回来,此时为第 $31$ 单位时间。

易于验证这是最优方案,因此答案为 $31$。

Constraints

对于所有数据,有 $1\le n\le 10^6$,$1\le t_i,x_i\le 10^9$,$t_i$ 两两不同。

  • Subtask $1$($10\%$):$n\le 5$;
  • Subtask $2$($15\%$):$n\le 20$;
  • Subtask $3$($10\%$):$n\le 100$;
  • Subtask $4$($20\%$):$n\le 5000$;
  • Subtask $5$($25\%$):$n\le 2\times 10^5$;
  • Subtask $6$($20\%$):无特殊限制。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$