Bài tập về nhà

Năm học mới tại Hogwarts đã bắt đầu, và các học sinh phải hoàn thành hàng loạt bài tập được giao bởi các giáo sư. Mỗi bài tập có một thời hạn nộp và cần một khoảng thời gian nhất định để hoàn thành.

Một học sinh bắt đầu làm bài từ thời điểm $0$. Tại mỗi thời điểm, học sinh chỉ có thể làm một bài tập duy nhất (không thể làm song song). Một bài tập được coi là hoàn thành đúng hạn nếu thời điểm hoàn thành không vượt quá thời hạn nộp của bài đó.

Cho $N$ bài tập, bài tập thứ $i$ cần $t_i$ đơn vị thời gian để hoàn thành và có thời hạn nộp là $d_i$. Hãy tìm số lượng bài tập tối đa mà học sinh có thể hoàn thành đúng hạn.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$ — số lượng bài tập.
• $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $t_i$ và $d_i$ — thời gian cần để hoàn thành và thời hạn nộp của bài tập thứ $i$.

Dữ liệu ra

• In ra một số nguyên duy nhất — số lượng bài tập tối đa có thể hoàn thành đúng hạn.

Ràng buộc

• $1\le N\le 2\times {10}^5$
• $1\le t_i\le d_i\le {10}^9$

Ví dụ

Ghi chú

Học sinh có thể chọn thứ tự làm bài tùy ý. Mỗi bài tập phải được làm liên tục từ đầu đến cuối (không được tạm dừng giữa chừng).