Vương quốc JOI có \(N\) cư dân, được đánh số từ \(1\) đến \(N\). Cư dân \(i\) (\(1 \le i \le N\)) sống tại tọa độ \(X_i\) trên trục số và có mức ảnh hưởng \(E_i\). Nhiều cư dân có thể sống tại cùng một tọa độ. Cư dân có mức ảnh hưởng càng lớn thì khả năng quảng bá càng cao, nhưng cũng càng thận trọng khi mua sách.

Rie đã xuất bản một cuốn sách về tin học. Để khuyến khích nhiều người mua sách, cô có thể tặng sách cho một số cư dân. Khi Rie tặng sách cho cư dân \(i\) (\(1 \le i \le N\)), người đó sẽ có sách của cô. Ngoài ra, trong số các cư dân chưa có sách, mọi cư dân \(j\) (\(1 \le j \le N\)) thỏa mãn điều kiện sau đều sẽ mua sách và có được một bản:

Khoảng cách trên trục số giữa cư dân \(i\) và cư dân \(j\) không vượt quá \(E_i - E_j\), tức là \(\lvert X_i - X_j \rvert \le E_i - E_j\).

Nếu mọi cư dân đều đọc sách của Rie, các kỳ Olympic Tin học sẽ được biết đến rộng rãi hơn. Hãy tìm số cư dân ít nhất mà Rie cần tặng sách để tất cả cư dân của vương quốc JOI đều có sách của cô.

Dữ liệu vào

Dữ liệu vào có dạng:

N
X_1 E_1
X_2 E_2
...
X_N E_N

Dữ liệu ra

In trên một dòng số cư dân ít nhất mà Rie cần tặng sách.

Ràng buộc

• \(1 \le N \le 500\,000\).
• \(1 \le X_i \le 10^9\) (\(1 \le i \le N\)).
• \(1 \le E_i \le 10^9\) (\(1 \le i \le N\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(10\) điểm: \(E_1 = E_2 = \cdots = E_N\).
2. \(23\) điểm: \(N \le 16\).
3. \(36\) điểm: \(N \le 1000\).
4. \(31\) điểm: Không có ràng buộc bổ sung.

Ví dụ

4
4 2
2 3
3 4
6 5

2

3
7 10
10 10
7 10

2

10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019

5

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.