Có ~N~ người dân sống ở ~1~ thành phố. Người thứ ~i~ sống ở vị trí ~x_i~ trên trục số và có sức ảnh hưởng là ~e_i~. Chủ tịch của thành phố đang muốn đẩy mạnh phong trào học tin nên họ muốn mọi người trong thành phố đều có sách tin học. Để làm điều này chủ tịch muốn tặng sách cho ~1~ số người trong thành phố và để những người này đi quảng bá sách cho họ. Cụ thể nếu người ~i~ có sách thì người ~j~ cũng sẽ đi mua sách nếu ~|x_i-x_j|\le e_i-e_j~. Hỏi chủ tịch cần phải tặng ít nhất bao nhiêu quyển sách để sau đó mọi người dân đều có sách.
Input
Dòng đầu tiên nhập vào số nguyên dương ~N~ ~(1\le N\le5\cdot10^5)~ chỉ số lượng người dân.
~N~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên ~x_i~ và ~e_i~ chỉ vị trí và sức ảnh hưởng của người dân thứ ~i~ ~(1\le x_i,e_i \le 10^9)~.
Output
In ra số lượng sách tối thiểu cần phải phát miễn phí cho người dân để sau đó mọi người đều có sách.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~10~ | ~e_1 = e_2 = · · · = e_N.~ |
2 | ~20~ | ~N ≤ 16.~ |
3 | ~30~ | ~N ≤ 1 000.~ |
4 | ~40~ | Không có điều kiện gì thêm. |
Sample Input 1
4
4 2
2 3
3 4
6 5
Sample Output 1
2
Sample Input 2
3
7 10
10 10
7 10
Sample Output 2
2
Notes
Giải thích test ví dụ ~1~:
Ví dụ, nếu Chủ tịch quyên tặng sách theo cách sau, tất cả cư dân trong Thành phố sẽ nhận được sách của Chủ tịch.
Chủ tịch tặng một bản sách cho Cư dân 3.
Vì ~|X_3 - X_1| = 1~ và ~E_3 - E_1 = 2~, Cư dân 1 sẽ mua một bản sách của Chủ tịch và nhận được nó.
Vì ~|X_3 - X_2| = 1~ và ~E_3 - E_2 = 1~, Cư dân 2 sẽ mua một bản sách của Chủ tịch và nhận được nó.
Vì ~|X_3 - X_4| = 3~ và ~E_3 - E_4 = -1~, Cư dân 4 sẽ không mua một bản sách của Chủ tịch.
Do đó, Cư dân 1, 2, 3 sẽ nhận được sách của Chủ tịch.
Chủ tịch tặng một bản sách cho Cư dân 4. Vì tất cả cư dân ngoại trừ Cư dân 4 đã nhận được sách của Chủ tịch, cuối cùng tất cả cư dân trong Thành phố đều nhận được sách của Chủ tịch.
Vì không thể quyên tặng sách cho ít hơn hai cư dân mà vẫn đảm bảo tất cả cư dân trong Thành phố nhận được sách của Chủ tịch, nên đầu ra là 2.
Bình luận