Phòng thi Olympic Tin học là một hình chữ nhật. Chọn hai trục tọa độ song song với các bức tường và gốc tọa độ tại một góc phòng. Ủy ban đã chế tạo \(n\) thiết bị để theo dõi \(m\) thí sinh cần được giám sát.

Mỗi thiết bị \(i\) có thể được đặt theo một trong hai hướng:

• Theo hướng trục \(x\): theo dõi mọi thí sinh trong dải \(p_i \le y \le p_i+d_i\).
• Theo hướng trục \(y\): theo dõi mọi thí sinh trong dải \(p_i \le x \le p_i+d_i\).

Các giá trị \(p_i,d_i\) là số nguyên, có thể chọn riêng cho từng thiết bị, với \(d_i \ge 0\). \(d_i\) càng nhỏ thì giám sát càng chính xác. Có thể không dùng hết các thiết bị.

Mỗi thí sinh trong danh sách phải được ít nhất một thiết bị hướng \(x\) và ít nhất một thiết bị hướng \(y\) theo dõi. Thí sinh đứng trên biên dải vẫn được theo dõi. Các thí sinh không di chuyển và có tọa độ đôi một khác nhau.

Gọi \(d_{\max}\) là giá trị \(d_i\) lớn nhất của các thiết bị. Hãy tìm giá trị nhỏ nhất có thể của \(d_{\max}\).

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa \(n,m\), với \(2 \le n \le 200000\), \(1 \le m \le 100000\).

\(m\) dòng tiếp theo, mỗi dòng chứa tọa độ nguyên \(x_j,y_j\) của một thí sinh, với \(0 \le x_j,y_j \le 1000000000\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là giá trị nhỏ nhất của \(d_{\max}\).

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm; tổng cộng \(100\) điểm. \(30\%\) số điểm ứng với \(n,m \le 100\) và mọi tọa độ không quá \(10000\). Một phần \(20\%\) khác ứng với \(n,m \le 1000\).

Ví dụ

4 5
4 9
2 4
7 8
6 1
4 4

3