Công ty LCROBO tổ chức kiểm tra tính năng sản phẩm của ~N~ robot. Mỗi lần kiểm tra nhân viên kỹ thuật sẽ cho những con robot đứng trên đường thử theo hàng ngang, nó như một trục số nguyên. Để đảm bảo an toàn trong quá trình kiểm tra, các robot phải đứng càng xa nhau càng tốt. Trên đường thử, có một số đoạn đã bố trí trạm sạc nên robot không thể đứng vào những vị trí đó, những đoạn Robot có thể đứng được không giao nhau và đoạn thứ ~i~ được mô tả bằng hai số nguyên ~A_i, B_i~. Robot có thể đứng tại một vị trí tọa độ nguyên trên những đoạn này.

Gọi ~L~ là khoảng cách giữa hai robot đứng gần nhau nhất.

Yêu cầu: Hãy tìm giá trị lớn nhất của ~L~ để xếp đủ ~N~ robot trong một lần kiểm tra.

Input

• Dòng 1: Hai số nguyên dương ~N, M~ ~(2 \le N \le 10^5; 1 \le M \le 10^5)~ tương ứng là số robot và số đoạn mà robot có thể đứng.

• ~M~ dòng tiếp theo: Mỗi dòng chứa hai số nguyên ~A_i, B_i~ ~(0 \le A_i \le B_i \le 10^{18}; 1 \le i \le M)~ xác định ~M~ đoạn robot có thể đứng được. Chú ý rằng các đoạn trên không giao nhau.

Output

In ra giá trị lớn nhất của ~L~. Chú ý rằng lời giải với ~L > 0~ luôn tồn tại.

Scoring

Sample Input 1

3 3
6 10
2 5
11 15

Sample Output 1

6

Sample Input 2

5 4
0 2
11 12
15 21
4 7

Sample Output 2

5

Sample Input 3

3 2
8 9
2 5

Sample Output 3

3

Notes

• Ở ví dụ 1: Không có trạm sạc nào nằm giữa các đoạn mà robot có thể đứng được. Vị trí đứng của ~3~ robot có thể là: ~2, 8~, và robot cuối cùng có thể đứng ở vị trí ~14~ hoặc ~15~.

• Ở ví dụ 2: Vị trí đứng của ~5~ robot có thể là: ~0, 5, 11, 16, 21~.

• Ở ví dụ 3: Vị trí đứng của ~3~ robot có thể là: ~2, 5~ và robot cuối cùng có thể đứng ở vị trí ~8~ hoặc ~9~.