408657: GYM103256 F Moss Growing

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Moss Growingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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.

Output

Print a single integer $$$-$$$ number of days that will pass for all cells to be occupied.

ExamplesInput
6 3
3 5
4 2
2 3
Output
3
Input
1000000000000000000 1
1 1
Output
999999999999999999
Note

You can see the explanation of the first example in the following images:

Note that the initial day is considered to be day 0.

加入题单

上一题 下一题 算法标签: