Trong một trò chơi, có ~N~ người chơi xếp thành một vòng tròn và được đánh số từ ~1~ đến ~N~ theo chiều kim đồng hồ. Trước khi trò chơi bắt đầu, sẽ có ~M~ lượt phát đồng xu cho người chơi với nguyên tắc như sau: mỗi lượt, chọn ngẫu nhiên hai số nguyên dương ~L~ và ~R~ (~L \le N, R \le N~), phát một đồng xu cho những người chơi từ số ~L~ đến số ~R~ theo chiều kim đồng hồ.

Yêu cầu: Cho trước ~N, M~ và các cặp số ~L, R~. Tìm số đồng xu lớn nhất mà người chơi được phát và số lượng người chơi đạt được số đồng xu như vậy.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~M~ là số lượng người chơi và số lượt phát đồng xu.
• ~M~ dòng sau, mỗi dòng gồm hai số nguyên dương ~L~ và ~R~ mô tả lượt phát đồng xu.

Output

• Gồm hai số nguyên dương là số đồng xu lớn nhất mà người chơi được phát và số lượng người chơi đạt được số đồng xu như vậy.

Sample Input 1

5 2
1 5
4 2

Sample Output 1

2 4