Phòng thí nghiệm Điện tử số của trường mở cửa trong ~T~ tiết học liên tiếp của học kỳ, các tiết được đánh số từ ~1~ đến ~T~. Có ~m~ nhóm sinh viên đăng ký làm đồ án tại phòng; nhóm thứ ~j~ đăng ký sử dụng phòng liên tục từ tiết ~l_j~ đến hết tiết ~r_j~ (tính cả hai tiết ~l_j~ và ~r_j~).

Phòng đủ rộng để nhiều nhóm cùng làm việc, nhưng mỗi nhóm có mặt cần một bộ thiết bị đo riêng. Để chuẩn bị thiết bị, cán bộ phụ trách muốn biết: vào tiết đông nhất có bao nhiêu nhóm cùng đăng ký, và có bao nhiêu tiết đông như vậy.

Yêu cầu

Với mỗi tiết ~x~ (~1 \le x \le T~), gọi ~c_x~ là số nhóm đăng ký sử dụng phòng trong tiết ~x~, tức là số chỉ số ~j~ thoả mãn ~l_j \le x \le r_j~. Hãy tìm giá trị lớn nhất ~K~ trong các số ~c_1, c_2, \ldots, c_T~ và số lượng tiết ~x~ có ~c_x = K~.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên ~T~ và ~m~;
• ~m~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~l_j~ và ~r_j~.

Kết quả ra

• Dòng thứ nhất ghi số ~K~ – số nhóm nhiều nhất cùng đăng ký một tiết;
• Dòng thứ hai ghi số lượng tiết có đúng ~K~ nhóm đăng ký.

Ràng buộc

~1 \le T \le 10^9~; ~1 \le m \le 2 \cdot 10^5~; ~1 \le l_j \le r_j \le T~.

• Subtask 1 (15% số điểm – test 01–04): ~T, m \le 100~;
• Subtask 2 (20% số điểm – test 05–08): ~T, m \le 5000~;
• Subtask 3 (35% số điểm – test 09–14): ~T \le 10^6~;
• Subtask 4 (30% số điểm – test 15–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

10 4
2 5
4 8
7 9
1 1

Kết quả ra mẫu 1

2
4

Giải thích

Số nhóm đăng ký ở các tiết ~1, 2, \ldots, 10~ lần lượt là ~1, 1, 1, 2, 2, 1, 2, 2, 1, 0~. Giá trị lớn nhất là ~K = 2~, đạt được tại bốn tiết ~4~, ~5~, ~7~, ~8~ (hai khoảng tiết tách rời nhau).