Problem
Ghiaccio, Venedik sokaklarında yürümek istiyor. Ancak bugün oldukça sinirli ve bu da yürümesini zorlaştırıyor.
Venedik turistler arasında oldukça popüler bir şehir, ancak şehre yabancı bir şekilde doğru "Venezia" yerine "Venedik" diyorlar.
Bu Ghiaccio'yu çok kızdırır ama yürüyüşten sonra öfkeli kalmak istemez. Bu nedenle, bazen turistlerin yanından geçerken tekrar sinirlenmemek için kulaklarını tıkamaya karar verdi.
Ghiaccio, saniyede bir puan yenilenen dahili bir sakinlik çubuğuna sahiptir (Ghiaccio evden çıktığında bu çubuğun değeri sıfırdır).
Bununla birlikte, Ghiaccio d kişinin bulunduğu bir turist grubunun yanından geçerse, sakinliği d kadar azalır, çünkü şehrin adının yanlış telaffuz edilmesine sinirlenir. Ama Ghiaccio kulaklarını tıkayarak yanından geçerse sakinliği azalmaz.
Zamanın bir noktasında sakinlik ölçeği negatif olursa Ghiaccio çılgına döner ki bu son derece kabul edilemez.
Ghiaccio Venedik'i çok iyi biliyor, bu yüzden yürüyüş sırasında n turist grubunun yanından geçeceğini biliyor, her biri için t
i sayısıyla ikinci sırada olacağı biliniyor ve bunda grupta d< sub>i kişi olacak.
Bu bilgilere dayanarak, Ghiaccio'nun yürürken çılgına dönmemesi için kulaklarını en az kaç kez tıkaması gerektiğini hesaplayın.
Giriş:
İlk satır tek bir tamsayı içerir n (1 ≤ n ≤ 200000) — Ghiaccio'nun etrafından geçeceği turist gruplarının sayısı.
Ardından, her biri boşlukla ayrılmış iki tam sayı içeren n satır gelir: t
i ve d
i (1 ≤ t
i ,&thinsp ;d
i ≤ 10
9) — Ghiaccio'nun i'nci turist grubunun yanından geçeceği saniyenin sayısı ve içindeki kişi sayısı. Tüm t
i farklıdır ve artan sıradadır.
Çıktı:
Tek bir tamsayı yazdır — Ghiaccio'nun çılgına dönmemek için kulaklarını en az kaç kez tıkaması gerekir.
Örnekler:
| Giriş |
Çıktı |
3
3 2
5 4
6 3
| 1 |
5
1 2
3 2
5 3
6 2
7 3
| 2 |
Açıklamalar:
İlk örnekte, Ghiaccio ikinci grubun yanından geçerken kulaklarını tıkamak zorunda kalıyor.
Ardından, üçüncü saniyenin sonunda, sakinliği 1'e eşit olacaktır (yürüyüşün her saniyesi için 3'ü telafi etti, ancak birinci gruptan geçerken 2 azaldı).
Beşinci saniyenin sonunda sakinlik 3'e eşit olacaktır (ikinci gruptan sakinlik azalmaz çünkü Ghiaccio geçerken kulaklarını tıkamıştır).
Ve altıncı saniyenin sonunda sakinlik 3+1-3 = 1'e eşit olacak.
Ayrıca sakinliği hiç azalmaz.