Để triển khai kế hoạch học online sắp tới cho 1 môn học, có N lớp học online được đánh số hiệu từ 1 đến N. Lớp học thứ i có thời điểm bắt đầu S_i và thời điểm kết thúc F_i.

Tại mỗi thời điểm trong mỗi phòng học có không quá một lớp học diễn ra, ngoại trừ trường hợp thời điểm kết thúc một lớp học có thể đồng thời là thời điểm bắt đầu của một lớp học khác.

Yêu cầu: Hãy xếp phòng học cho tất cả các lớp học sao cho số phòng cần sử dụng là ít nhất.

Nhập từ file văn bản theo quy cách như sau:

• Dòng thứ nhất ghi số nguyên dương N (N≤ 1000) là số lượng lớp học.
• Trên dòng thứ i (1 \leq i\leq N) trong N dòng tiếp theo ghi hai số nguyên dương S_i và F_i (0 \leq Si \lt Fi \leq 70000) tương ứng là thời điểm bắt đầu và thời điểm kết thúc của lớp học thứ i.

Ghi ra một số nguyên M là số phòng ít nhất cần.