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à, hãy xác định số món quà nhiều nhất mà một bạn học sinh được nhận và số bạn học sinh cùng nhận được số món quà nhiều nhất đó.

Input

• Dòng 1 chứa hai số nguyên dương ~n, m~ (~2 \le n \le 10^9~; ~1 \le m \le 10^5~)
• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a, k~ (~1 \le a \le 10^9~; ~1 \le k \le 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.

Sample Input 1

6 3
5 4
20 1
4 5

Sample Output 1

6 2