Some country X is a square of $N\times N$ cells. Its inhabitants use a coordinate system in which the lower-left and upper-right corners of the square have coordinates $(0, 0)$ and $(N, N)$. There are $K$ cities in the country, each at a point with integer coordinates.

Residents of country X move around the country parallel to the coordinate axes. To speed up travel to neighboring countries, the government has decided to build two highways. Highways must be perpendicular to each other and parallel to the coordinate axes. Each trunk will connect two opposite sides of the square.
The distance from the city to the highways will be the distance from the city to the nearest one. The government has decided to place highways so that the maximum distance from cities to highways is the minimum possible.
Your task is to find the optimal distance from the farthest city to the nearest highway.

Input format

• The first line contains two numbers $N$ and $K$ denoting the length of the side of the square and the number of cities respectively.
• The next $K$ lines contain two numbers denoting the coordinates of cities (from 0 to N).

Output format

Print the answer to the problem.

Constraints

$1 \le N \le 10^6\\ 1 \le K \le 4\times 10^4$