Problem
ギアッチョはヴェネツィアの街を歩きたいと思っています。しかし今日はかなりイライラして歩くのも困難
です。
ヴェネツィアは観光客の間で非常に人気のある都市ですが、観光客はこの都市のことを正しい「ヴェネツィア」ではなく、外国風に「ヴェネツィア」と呼んでいます
。
これにはギアッチョさんは非常に腹を立てましたが、散歩の後も激怒し続けることは望んでいませんでした。そこで、観光客の前を通るときは、二度と怒られないように時々耳を塞ぐことにした
のです。
ギアッチョには、1 秒ごとに 1 ポイントずつ回復する内部静穏バーがあります (ギアッチョが家を出ると、このバーの値はゼロになります)。
しかし、ギアッチョが d 人の観光客グループの前を通り過ぎると、彼の冷静さは d だけ減少します。彼は都市の名前の発音が間違っていることに腹を立てます。しかし、ギアッチョが耳をふさぎながら通り過ぎても、彼の冷静さは衰えることは
ありません。
ある時点で穏やかなスケールがマイナスになると、ギアッチョは凶暴化することになり、それは非常に容認できません
。
ギアッチョはヴェネツィアをよく知っているので、散歩中に n 組ほどの観光客グループとすれ違うことを知っています。それぞれのグループは t
i という番号の 2 番目のグループになることがわかっています。グループには d< sub>i 人がいます。
この情報に基づいて、ギアッチョが歩行中に暴走しないように耳を塞ぐ必要がある最小限の回数を計算してください。
入力:
最初の行には、単一の整数 n (1≤ n ≤ 200000) が含まれています。ギアッチョが通過する観光客グループの数
次に n 行が続き、各行にはスペースで区切られた 2 つの整数 t
i と d
i (1 ≤ t
i ,&thinsp) が含まれます。 ;d
i ≤ 10
9) —ギアッチョが i 番目の観光客グループとすれ違う秒数とその人数。すべての t
i は個別であり、昇順になっています。
出力:
単一の整数を出力します —ギアッチョが暴走しないように耳を塞ぐ必要がある最小限の回数。
例:
<本体>
| 入力 |
出力 |
3
3 2
5 4
6 3
| 1 |
5
1 2
3 2
5 3
6 2
7 3
| 2 |
説明:
最初の例では、ギアッチョは 2 番目のグループの近くを通過するときに耳を塞がなければなりません。
そして、3 秒目が終了するまでに、彼の冷静さは 1 になります (歩行の 1 秒ごとに 3 が補われますが、最初のグループを追い抜くと 2 減ります)。
5 秒目が終了するまでに、冷静さは 3 になります (ギアッチョが通過するときに耳を塞いだため、冷静さは 2 番目のグループから減少しません)。
そして6秒目が終わる頃には、静けさは3+1-3=1になります
。
さらに、彼の冷静さは決して衰えることはありません。