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

5 2 
1 5 
4 2

Sample Output

2 4

Giải thích

• Số đồng xu của mỗi người ở mỗi lượt phát đồng xu:
• Ban đầu: 0 0 0 0 0
• Lượt thứ nhất: 1 1 1 1 1
• Lượt thứ hai: 2 2 1 2 2
• Vậy số lượng đồng xu lớn nhất là 2 và có 4 người được 2 đồng xu.

Subtask

• Có 60% số test: ~N, M \le 10^3~;
• Có 20% số test khác: ~N, M \le 10^5~;
• Có 20% số test còn lại: ~𝑁 \le 10^9 , M ≤ 10^5~