You are given a squared Petri dish represented by a grid of size $$$N * N$$$. Rows are numbered from $$$1$$$ to $$$N$$$ from top to bottom and columns are numbered from $$$1$$$ to $$$N$$$ from left to right. The cell located in the intersection between the $$$x$$$-th row and $$$y$$$-th column is denoted by the coordinates $$$(x,y)$$$.
There are $$$M$$$ small patches of moss initially. The $$$i$$$-th patch is located in the coordinates $$$(x_i,y_i)$$$. During the next days, the patches of moss will extend to the 8 neighboring cells day by day. That is, if in the $$$j$$$-day the cell $$$(x,y)$$$ is occupied, then during the $$$(j+1)$$$-th day the cells $$$(x-1,y-1)$$$, $$$(x-1,y)$$$, $$$(x-1,y+1)$$$, $$$(x,y-1)$$$, $$$(x,y+1)$$$, $$$(x+1,y-1)$$$, $$$(x+1,y)$$$ and $$$(x+1,y+1)$$$ will be occupied, as long as they are inside the grid.
How many days will pass for all cells to be occupied by the patches of moss?
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^{18}$$$ and $$$1 \leq M \leq min(N*N, 1000)$$$) $$$-$$$ size of the grid and number of initial patches of moss.
The next $$$M$$$ lines contain two integers each $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq N$$$) $$$-$$$ the coordinates of the patches.
It is guaranteed that all the coordinates are different.
Print a single integer $$$-$$$ number of days that will pass for all cells to be occupied.
6 3 3 5 4 2 2 3
3
1000000000000000000 1 1 1
999999999999999999
You can see the explanation of the first example in the following images:
Note that the initial day is considered to be day 0.
