分数: 266 分
问题陈述
某政府机关只有 1 服务窗口,提供服务 N 访客按顺序,编号 1, 2, \ldots, N。窗口只能服务 1 一次访客。
的 i第一位访客到达办公室的时间 A_i,并为他们提供服务需要 B_i 时间单位。保证到达时间按照其数量的顺序不递减,即 A_1 \leq A_2 \leq \cdots \leq A_N.
窗口可提供服务的时间 0 开始,始终按照访问者的顺序为访问者提供服务 1 致访客 N。访客服务 i 最早开始时间为 窗口免费,访客 i 已到达。出租 S_i 表示为访客提供服务的开始时间 i:
- S_1 = A_1
- S_i = \max(S_{i-1} + B_{i-1},\ A_i) (i \geq 2)
访客服务 i 结束时间 S_i + B_i.
找时间 S_N + B_N 最后一位访客(访客 N)结束。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 10^9
- 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数。
输入
N A_1 B_1 A_2 B_2 \vdots A_N B_N
- 第一行包含一个整数 N 代表访客数量。
- 以下 N 行各包含, i第线,到达时间 A_i 和服务期限 B_i 的 i第一个访客,以空格分隔。
输出
在一行上打印最后一位访客的服务结束时间。
示例输入 1
3 0 3 1 2 5 4
示例输出 1
9
示例输入 2
4 2 1 10 2 10 3 20 1
示例输出 2
21
示例输入 3
8 0 5 1 3 4 2 10 7 10 1 15 4 30 6 31 2
示例输出 3
38
示例输入 4
15 0 2 0 3 1 5 2 1 2 4 3 2 5 6 8 1 8 3 10 2 13 5 13 1 20 4 21 2 21 7
示例输出 4
48
示例输入 5
1 1000000000 1000000000
示例输出 5
2000000000