Có ~n~ học sinh được nhận quà từ ~m~ nhà tài trợ. Các học sinh được đánh số từ 1 tới ~n~ và các nhà tài trợ được đánh số từ 1 tới ~m~. Các bạn học sinh đứng quanh một vòng tròn: Bên phải học sinh 1 là học sinh 2, bên phải học sinh 2 là học sinh 3, … bên phải học sinh ~n~ là học sinh 1.

Lần lượt từng nhà tài trợ sẽ trao một hộp quà cho một học sinh làm đại diện, hộp quà có thể chứa một hoặc nhiều món quà. Khi một học sinh nhận được hộp, bạn đó sẽ lấy ra đúng 1 món quà cho mình rồi chuyển hộp ngay cho bạn bên phải và quá trình cứ tiếp tục như vậy cho tới khi trong hộp không còn món quà nào.

Yêu cầu: Sau khi tất cả các nhà tài trợ đã trao quà, cho biết số món quà nhiều nhất một bạn học sinh được nhận và số bạn học sinh cùng nhận nhiều món quà nhất.

Input

Dòng 1 chứa hai số nguyên dương ~n, m~ (~2 ≤ n ≤ 10^9; 1 ≤ m ≤ 10^5~)

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a, k~ (~1 ≤ a ≤ 10^9; 1 ≤ k ≤ n~) tương ứng với thông tin: Một nhà tài trợ trao hộp chứa ~a~ món quà cho học sinh thứ ~k~

Output

Ghi ra một dòng gồm hai số nguyên ~p, q~ trong đó ~p~ là số món quà nhiều nhất mà một bạn học sinh được nhận, còn ~q~ là số bạn học sinh cùng nhận nhiều món quà nhất.

Test mẫu

Input

6 3
5 4
20 1
4 5

Output

6 2

Giải thích: http:///ibb.co/1ffGWsZS

Subtasks

~50\%~ số điểm ứng với các test có ~n, m, a ≤ 10^3~

~30\%~ số điểm ứng với các test có ~n, m ≤ 10^5~

~20\%~ số điểm còn lại không có ràng buộc bổ sung