← 返回题目列表

AtCoder · awc0023_b

B. 巴士之旅

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

分数: 266 分

问题陈述

高桥正在运营观光巴士旅游。在这次旅行中,巴士会按顺序停靠多个站点来接载乘客。

这次旅行有 N 停靠点,编号停靠点 1,停止 2,...,停止 N 从出发点开始依次排列。停止 1 是第一站,停止 N 是最终目的地。

巴士最初是空的(在车站上车之前) 1).

在每个站点 i (1 \leq i \leq N), A_i 新乘客登上公交车。

此外,在每个站点 i (1 \leq i \leq N - 1),登机后, B_i 乘客在前往下一站的行程中下车并离开团 i + 1。但是,如果当前公交车上的乘客人数少于 B_i,车上乘客全部下车。

综上所述,每一站的流程 i 如下:

  1. A_i 新乘客登上公交车。
  2. If i \leq N - 1,在前往下一站的行程中, \min(\text{current number of passengers}, B_i) 乘客下车。如果 i = N,没有乘客下车。

查找车站上车时公交车上的乘客人数 N 已完成。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq B_i \leq 10^9 (1 \leq i \leq N - 1)
  • 所有输入值均为整数。

输入

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
A_N
  • 第一行包含一个整数 N,代表停靠次数。
  • 的 (i + 1)- 第行 (1 \leq i \leq N - 1) 包含在车站上车的乘客人数 i, A_i,以及下车乘客人数, B_i,用空格分隔。
  • 的 (N + 1)-第行仅包含 A_N, 车站上车乘客人数 N.

输出

在车站上车时单行打印公交车上的乘客人数 N 已完成。


样本输入 1

3
5 2
3 1
4

示例输出 1

9

示例输入 2

3
2 10
1 5
3

示例输出 2

3

示例输入 3

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

示例输出 3

13

示例输入 4

10
1000000000 500000000
1000000000 200000000
500000000 1000000000
300000000 100000000
0 999999999
1000000000 1000000000
999999999 0
0 500000000
500000000 1000000000
123456789

示例输出 4

123456789

示例输入 5

2
0 0
0

示例输出 5

0