Trên một mặt phẳng tọa độ, có \(m\) vết bẩn có tọa độ \((x_i,y_i)\). Để làm sạch khu vực này, người ta sử dụng tối đa \(n\) con robot.
Mỗi con robot khi hoạt động sẽ chọn một cấu hình dọn dẹp cố định: hoặc dọn theo chiều ngang, hoặc dọn theo chiều dọc với độ dài quét \(w\), cụ thể:

• Nếu dọn ngang, robot chọn một vị trí \(q\) và làm sạch toàn bộ vùng có hoành độ thuộc đoạn \([q,q+w]\).
• Nếu dọn dọc, robot chọn một vị trí \(p\) và làm sạch toàn bộ vùng có tung độ thuộc đoạn \([p,p+w]\).

Một vết bẩn được coi là dọn sạch hoàn toàn khi vị trí của nó đồng thời được phủ bởi ít nhất một robot dọn ngang và ít nhất một robot dọn dọc. Hãy tìm giá trị \(w\) nhỏ nhất để có thể dọn sạch tất cả \(m\) vết bẩn.

Input

Từ file ROBOT.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\) (\(2\le n\le 10^5,\) \(1\le m\le 10^5\)) lần lượt là số lượng robot tối đa và số lượng vết bẩn.
• Mỗi dòng trong \(m\) dòng tiếp theo chứa hai số nguyên \(x_i,y_i\) (\(0\le x_i,y_i\le 10^9\)) mô tả tọa độ của một vết bẩn.

Output

Ghi ra file ROBOT.OUT một dòng duy nhất chứa một số nguyên là giá trị \(w\) nhỏ nhất tìm được.

Example

3 4
1 2
3 5
4 2
8 5

3

Scoring

• Subtask \(1\) (\(60\%\)): \(n=2\).
• Subtask \(2\) (\(20\%\)): \(x_1=x_2=x_3=...=x_n\); đảm bảo \(w\le 1000\).
• Subtask \(3\) (\(20\%\)): Không có ràng buộc gì thêm.