← 返回题目列表

Codeforces · 116/A

A. 电车

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

线性王国只有一条有轨电车线路。它有 n 个车站,按照有轨电车的运行顺序从 1 到 n 编号。在第 i 站,ai 乘客下车,而 bi 乘客上车。电车在到达第一站之前就已经空了。此外,当电车到达最后一站时,所有乘客都会下车,这样车站就空了。

您的任务是计算有轨电车的最小容量,以便任何时候电车内的人数都不会超过此容量。请注意,在每个车站,所有离开的乘客都会在任何进入的乘客进入电车之前退出。

输入

第一行包含一个数字 n (2 ≤ n ≤ 1000) — 电车的停靠站数。

接下来是 n 行,每行包含两个整数 ai 和 bi (0 ≤ ai, bi ≤ 1000) — 在第 i 站下车的乘客数量,以及在第 i 站上车的乘客数量。站点按照有轨电车的运行顺序从第一个站点到最后一个站点给出。

- 在给定站点下车的人数不超过电车即将到达该站点之前的总人数。更正式地说,$$$$。这特别意味着a1 = 0。
- 在最后一站,所有乘客都下了电车,电车变得空荡荡的。更正式地说,$$\sum_{j=1}^{n-1} b_j - \sum_{j=1}^{n-1} a_j = a_n$$。
- 没有乘客将在最后一站进入火车。即bn = 0。

输出

打印一个整数,表示有轨电车的最小可能容量(允许为 0)。

示例

输入 #1

4
0 3
2 5
4 2
4 0

输出 #1

6

注意

对于第一个示例,容量 6 就足够了:

- 在第一站,到达前电车内的乘客数量为0。然后,3名乘客进入电车,电车内的乘客数量变为3。
- 在第二站,2 名乘客下了电车(1 名乘客留在车内)。然后,5名乘客进入电车。目前电车内共有6名乘客。
- 在第三站,4 名乘客下了电车(2 名乘客留在车内)。然后,2名乘客进入电车。现在电车内有4名乘客。
- 最后,电车内剩余的所有乘客在最后一站下车。目前电车内没有乘客,符合限制条件。

由于电车内的乘客人数永远不会超过 6 人,因此 6 人就足够了。此外,有轨电车的载客量不可能少于 6 人。因此,6 是正确答案。