← 返回题目列表

AtCoder · awc0096_a

A. 接收窗口的关闭时间

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

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