Problem
Ghiaccio muốn đi dạo trên đường phố Venice. Tuy nhiên, mấy hôm nay anh khá cáu kỉnh, đi lại khó khăn.
Venice là một thành phố khá nổi tiếng đối với khách du lịch, tuy nhiên, họ gọi thành phố là "Venice" theo cách nước ngoài, thay vì "Venezia" chính xác.
Điều này khiến Ghiaccio rất tức giận, nhưng anh ấy không muốn tiếp tục tức giận sau cuộc dạo chơi. Vì vậy, anh quyết định thỉnh thoảng sẽ bịt tai khi có khách du lịch đi ngang qua để không phải tức giận nữa.
Ghiaccio có một thanh bình tĩnh bên trong sẽ bổ sung một điểm mỗi giây (khi Ghiaccio rời khỏi nhà, giá trị của thanh này bằng 0).
Tuy nhiên, nếu Ghiaccio đi ngang qua một nhóm khách du lịch, trong đó có d người, thì sự bình tĩnh của anh ta sẽ giảm đi d, bởi vì anh ấy tức giận vì phát âm sai tên thành phố. Nhưng nếu Ghiaccio bịt tai đi ngang qua, sự bình tĩnh của anh ta vẫn không giảm đi.
Nếu tại một thời điểm nào đó, thang đo bình tĩnh trở nên tiêu cực, thì Ghiaccio sẽ trở nên điên cuồng, điều này cực kỳ khó chấp nhận.
Ghiaccio biết rất rõ về Venice, vì vậy anh ấy biết rằng trong khi đi bộ, anh ấy sẽ đi ngang qua n nhóm khách du lịch, với mỗi nhóm được biết rằng nó sẽ ở vị trí thứ hai với số t
i và trong đó nhóm sẽ có d
i người.
Dựa vào thông tin này, hãy tính số lần Ghiaccio phải bịt tai ít nhất để không bị phát điên khi đi bộ.
Đầu vào:
Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 200000) — số nhóm khách du lịch mà Ghiaccio sẽ đi qua.
Sau đó n dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách: t
i và d
i (1 ≤ t
i ,&thinsp ;d
i ≤ 10
9) — số thứ hai mà Ghiaccio sẽ đi ngang qua nhóm khách du lịch thứ i và số người trong đó. Tất cả t
i đều khác biệt và theo thứ tự tăng dần.
Đầu ra:
In một số nguyên duy nhất — số lần Ghiaccio phải bịt tai tối thiểu để không nổi điên.
Ví dụ:
| Đầu vào |
Đầu ra |
3
3 2
5 4
6 3
| 1 |
5
1 2
3 2
5 3
6 2
7 3
| 2 |
Giải thích:
Trong ví dụ đầu tiên, Ghiaccio phải bịt tai khi đi ngang qua nhóm thứ hai.
Sau đó, vào cuối giây thứ ba, sự bình tĩnh của anh ta sẽ bằng 1 (3 anh ta bù cho mỗi giây đi bộ, nhưng giảm 2 khi đi qua nhóm đầu tiên).
Đến cuối giây thứ năm, độ điềm tĩnh sẽ bằng 3 (độ điềm tĩnh không giảm so với nhóm thứ hai, vì Ghiaccio bịt tai khi đi qua).
Và đến hết giây thứ sáu, độ lặng sẽ bằng 3+1-3 = 1.
Hơn nữa, sự bình tĩnh của anh ấy không bao giờ giảm đi.