Module: 贪心算法


Problem

6 /9


Ghiaccio 走在威尼斯

Problem

Ghiaccio 想走在威尼斯的街道上。不过,他今天脾气暴躁,走路都有些吃力。
威尼斯是一个颇受游客欢迎的城市,然而,他们用外国的方式称呼这座城市为“Venice”,而不是正确的“Venezia”。
这让 Ghiaccio 非常生气,但他不想在散步后继续生气。因此,他决定有时路过游客时会堵住耳朵,以免再次上火。

Ghiaccio 有一个内部平静条,每秒补充一点(当 Ghiaccio 离开房子时,该条的值为零)。
然而,如果 Ghiaccio 经过一个旅游团,其中有 d 个人,那么他的冷静度会降低 d,因为他对城市名称的错误发音感到生气。但如果吉亚乔捂着耳朵从身边走过,他的冷静也不会减少。
如果在某个时间点平静的尺度变成负值,那么 Ghiaccio 就会变得狂暴,这是非常不可接受的。

Ghiaccio 非常了解威尼斯,所以他知道在步行期间他将经过大约 n 个旅游团,已知每个旅游团将排在第二个,编号为 ti,而在这个组里会有di个人。

根据这些信息,计算 Ghiaccio 最少要塞住耳朵的次数,这样他走路时才不会发疯。

输入:
第一行包含一个整数 n (1 ≤ n ≤ 200000) — Ghiaccio 将经过的旅游团数量。

然后是 n 行,每行包含两个以空格分隔的整数:ti 和 di (1 ≤ ti ,&thinsp ;di ≤ 109) — Ghiaccio 将经过第 i 个旅游团的秒数,以及其中的人数。所有 ti 都是不同的,并且按升序排列。

输出:
打印单个整数—— Ghiaccio 必须堵住耳朵才能不发疯的最少次数。

示例:
  <正文>
说明:
在第一个例子中,Ghiaccio 在经过第二组附近时不得不塞住耳朵。 
然后到第三秒结束时,他的冷静度会等于1(3他每走一秒就补上,但是经过第一组减了2)。 
到第5秒结束时,冷静会等于3(冷静不会从第二组开始减少,因为Ghiaccio经过时堵住了耳朵)。
而到第六秒结束时,平静度将等于3+1-3 = 1。
此外,他的冷静从未减弱。
输入 输出
3
3 2
5 4
6 3
1
5
1 2
3 2
5 3
6 2
7 3
2