Bài 3

Bạn An có một bộ sách hay và muốn chia sẻ với các bạn trong câu lạc bộ đọc sách của trường. Có $N$ yêu cầu được mượn cuốn sách này từ các bạn trong câu lạc bộ, yêu cầu thứ $i$ ($1\le i\le N$) cho biết thời điểm mượn sách là $a_i$ và thời điểm trả là $b_i$. Bạn An có thể chấp nhận hoặc từ chối đối với một yêu cầu.

Yêu cầu: Hãy lập trình giúp bạn An chọn các yêu cầu mượn sách của các bạn sao cho đáp ứng được nhiều yêu cầu nhất. Đảm bảo khoảng thời gian sử dụng của hai yêu cầu là không giao nhau.

Dữ liệu vào từ tệp văn bản BAI3.INP gồm:

• Dòng đầu tiên chứa số nguyên dương $N$ ($N\le 10^4$).
• Dòng thứ $i$ trong số $N$ dòng tiếp theo chứa hai số nguyên dương $a_i, b_i$ với $(0<a_i<b_i\le 32000)$ ($1\le i\le N$).

Kết quả ghi ra tệp văn bản BAI3.OUT một số nguyên $K$ là số các yêu cầu được chấp nhận.

• Subtask $1$ ($30\%$ số điểm):
  • $N\le 100$
  • $a_i<b_i\le 10^3$
• Subtask $2$ ($30\%$ số điểm):
  • $100<N\le 10^3$
  • $a_i<b_i\le 10^3$
• Subtask $3$ ($40\%$ số điểm): Theo dữ liệu đề bài.