ROBOTS


Submit solution

Points: 30
Time limit: 1.0s
Memory limit: 493M

Problem type

Ở nhà máy nọ có N chú rô bốt được xếp thành đường thẳng đang bận rộn làm việc trên dây chuyền. Chú rô bốt thứ i nằm ở vị trí Xi có cánh tay dài Li nên chú có thể làm các công việc trong khoảng từ (Xi − Li, Xi + Li). Để tránh sự va chạm giữa các chú rô bốt khi đang làm việc, người ta quyết định sẽ bỏ đi một số rô bốt(hoặc không bỏ rô bốt nào) sao cho không có hai rôbốt nào va chạm nhau khi đang làm việc nhưng họ cũng muốn giữ lại nhiều rô bốt nhất có thể.

Yêu cầu: Tính xem nhà máy có thể giữ được nhiều nhất bao nhiêu con rô bốt.

Dữ liệu

• Dòng đầu tiên, gồm một số nguyên N.

• N dòng tiếp theo, mỗi dòng gồm hai số nguyên Xi và Li.

Kết quả

• Gồm một dòng duy nhất là số rô bốt nhiều nhất có thể giữ lại.

Sample Input

4
2 4
4 3
9 3
100 5

Sample Output

3

Sample Input

5
10 1
2 1
4 1
6 1
8 1

Sample Output

5

Giới hạn Trong tất cả các test:

• 1 ≤ N ≤ 100000.
• 1 ≤ Xi ≤ 10^9 (1 ≤ i ≤ N).
• 1 ≤ Li ≤ 10^9 (1 ≤ i ≤ N).
• Nếu i khác j, Xi khác Xj.

Comments

There are no comments at the moment.