分数: 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 如下:
- A_i 新乘客登上公交车。
- 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