Problem
Ghiaccio 想走在威尼斯的街道上。不过,他今天脾气暴躁,走路都有些吃力。
威尼斯是一个颇受游客欢迎的城市,然而,他们用外国的方式称呼这座城市为“Venice”,而不是正确的“Venezia”。
这让 Ghiaccio 非常生气,但他不想在散步后继续生气。因此,他决定有时路过游客时会堵住耳朵,以免再次上火。
Ghiaccio 有一个内部平静条,每秒补充一点(当 Ghiaccio 离开房子时,该条的值为零)。
然而,如果 Ghiaccio 经过一个旅游团,其中有 d 个人,那么他的冷静度会降低 d,因为他对城市名称的错误发音感到生气。但如果吉亚乔捂着耳朵从身边走过,他的冷静也不会减少。
如果在某个时间点平静的尺度变成负值,那么 Ghiaccio 就会变得狂暴,这是非常不可接受的。
Ghiaccio 非常了解威尼斯,所以他知道在步行期间他将经过大约 n 个旅游团,已知每个旅游团将排在第二个,编号为 t
i,而在这个组里会有d
i个人。
根据这些信息,计算 Ghiaccio 最少要塞住耳朵的次数,这样他走路时才不会发疯。
输入:
第一行包含一个整数 n (1 ≤ n ≤ 200000) — Ghiaccio 将经过的旅游团数量。
然后是 n 行,每行包含两个以空格分隔的整数:t
i 和 d
i (1 ≤ t
i ,&thinsp ;d
i ≤ 10
9) — Ghiaccio 将经过第 i 个旅游团的秒数,以及其中的人数。所有 t
i 都是不同的,并且按升序排列。
输出:
打印单个整数—— Ghiaccio 必须堵住耳朵才能不发疯的最少次数。
示例:
<正文>
输入 |
输出 |
3
3 2
5 4
6 3
| 1 |
5
1 2
3 2
5 3
6 2
7 3
| 2 |
表>
说明:
在第一个例子中,Ghiaccio 在经过第二组附近时不得不塞住耳朵。
然后到第三秒结束时,他的冷静度会等于1(3他每走一秒就补上,但是经过第一组减了2)。
到第5秒结束时,冷静会等于3(冷静不会从第二组开始减少,因为Ghiaccio经过时堵住了耳朵)。
而到第六秒结束时,平静度将等于3+1-3 = 1。
此外,他的冷静从未减弱。