Ở phía đông nam Canada, tại khu vực biên giới với Hoa Kỳ, có năm hồ nổi tiếng được gọi chung là Ngũ Đại Hồ. Nhân dịp IOI được tổ chức tại Canada, nhiều kế hoạch khai thác thuyền du lịch trên hồ Ontario, hồ gần địa điểm tổ chức nhất, đã được đề xuất.

Mỗi kế hoạch khai thác thuyền du lịch nối hai điểm trên bờ hồ. Có tất cả \(N\) kế hoạch; kế hoạch thứ \(i\) cho thuyền hoạt động giữa điểm \(s_i\) và điểm \(t_i\). Ở đây, điểm \(x\) là điểm đạt được khi xuất phát từ điểm cực đông của hồ rồi đi dọc theo bờ hồ ngược chiều kim đồng hồ một quãng đường \(x\) mét. Chiều dài một vòng bờ hồ là \(500\,000\) mét.

Người ta muốn thực hiện càng nhiều kế hoạch càng tốt. Tuy nhiên, để tránh các thuyền va chạm nhau, không được có hai tuyến thuyền giao nhau.

Yêu cầu

Cho \(N\) kế hoạch khai thác thuyền, hãy viết chương trình tìm số kế hoạch lớn nhất có thể thực hiện.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn.

• Dòng đầu tiên chứa số nguyên \(N\), là số kế hoạch khai thác thuyền du lịch.
• Dòng thứ \(i+1\) với \(1\le i\le N\) chứa hai số nguyên \(s_i\), \(t_i\), cách nhau bởi dấu cách, là hai điểm được nối trong kế hoạch thứ \(i\).

Tất cả \(2N\) giá trị \(s_1,\ldots,s_N,t_1,\ldots,t_N\) đều khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là số kế hoạch lớn nhất có thể thực hiện trong các kế hoạch đã cho.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(256\) MB.

• \(1\le N\le 2\,000\).

• \(0\le s_i<500\,000\) và \(0\le t_i<500\,000\) với mọi \(1\le i\le N\).
• Tất cả \(2N\) tọa độ đầu mút đều khác nhau.

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ kiểm thử có tổng cộng \(40\) điểm thỏa mãn \(N\le 200\).

Ví dụ

5
50000 150000
450000 100000
200000 300000
260000 350000
0 230000

3