Problem
Ghiaccio mahu berjalan di jalan-jalan Venice. Namun, hari ini dia agak meragam sehingga sukar untuk berjalan.
Venice ialah bandar yang agak popular di kalangan pelancong, yang bagaimanapun, memanggil bandar itu "Venice" dengan cara asing, bukannya "Venezia" yang betul.
Ini membuatkan Ghiaccio sangat marah, tetapi dia tidak mahu terus marah selepas berjalan. Oleh itu, dia memutuskan kadang-kadang dia akan memasang telinga apabila melalui pelancong supaya tidak marah lagi.
Ghiaccio mempunyai bar ketenangan dalaman yang diisi semula sebanyak satu mata sesaat (apabila Ghiaccio meninggalkan rumah, nilai bar ini ialah sifar).
Walau bagaimanapun, jika Ghiaccio melalui kumpulan pelancong, yang terdapat d orang, maka ketenangannya berkurangan sebanyak d, kerana dia marah kerana salah sebutan nama bandar itu. Tetapi jika Ghiaccio lewat, memasang telinga, ketenangannya tidak akan berkurangan.
Jika pada satu ketika skala tenang menjadi negatif, maka Ghiaccio akan mengamuk, yang sangat tidak boleh diterima.
Ghiaccio mengenali Venice dengan baik, jadi dia tahu bahawa semasa berjalan-jalan dia akan melalui tentang n kumpulan pelancong, yang setiap satu diketahui bahawa ia akan berada di kedua dengan nombor t
i dan dalam ini kumpulan akan ada d< sub>i orang.
Berdasarkan maklumat ini, hitung bilangan minimum Ghiaccio perlu memasang telinganya supaya dia tidak mengamuk semasa berjalan.
Input:
Baris pertama mengandungi integer tunggal n (1 ≤ n ≤ 200000) — bilangan kumpulan pelancong yang akan dilalui oleh Ghiaccio.
Kemudian n baris mengikuti, setiap satu mengandungi dua integer yang dipisahkan ruang: t
i dan d
i (1 ≤ t
i ,&thinsp ;d
i ≤ 10
9) — bilangan detik di mana Ghiaccio akan melepasi kumpulan pelancong ke-i, dan bilangan orang di dalamnya. Semua t
i adalah berbeza dan berada dalam tertib menaik.
Output:
Cetak satu integer — bilangan minimum Ghiaccio perlu memasang telinganya agar tidak mengamuk.
Contoh:
| Input |
Output |
3
3 2
5 4
6 3
| 1 |
5
1 2
3 2
5 3
6 2
7 3
| 2 |
Penjelasan:
Dalam contoh pertama, Ghiaccio perlu memasang telinga semasa melintas berhampiran kumpulan kedua.
Kemudian pada penghujung saat ketiga, ketenangannya akan bersamaan dengan 1 (3 dia menebus setiap saat berjalan, tetapi menurun sebanyak 2 melalui kumpulan pertama).
Menjelang penghujung saat kelima, ketenangan akan bersamaan dengan 3 (ketenangan tidak akan berkurangan daripada kumpulan kedua, kerana Ghiaccio memasang telinga semasa dia berlalu).
Dan pada penghujung saat keenam, ketenangan akan sama dengan 3+1-3 = 1.
Tambahan pula, ketenangannya tidak pernah berkurangan.