I - > Pieces
Flavor
2
s
1024
MB
100
点
問題文
$N\times 10^9$ のマス目があり、$i$ 行 $j$ 列 $(1\leq i\leq N,1\leq j\leq 10^9)$ のマスを $(i,j)$ で表します。このマス目上に $M$ 個のコマが置かれており、$i$ 番目のコマは $(X_i,Y_i)$ にあります（同じマスに $2$ 個以上のコマがあることもあります）。これらのコマに対し、あなたは次の操作を好きな回数（$0$ 回以上）繰り返すことができます。
- 操作：$(x,y)$ に置かれたコマを $(x-1,y-1),(x+1,y-1)$ のどちらかに動かす。ただし動かす先のマスに他のコマがあってもよいが、コマがマス目の外に出る動かし方はできない。
操作を終えた後、スコア を次のように定めます。
- 各 $1\leq x\leq N$ に対し、$(x,y)$ にコマがあるような最大の $y$ の値を $f(x)$ とする（$x$ 行目に一つもコマが置かれていない場合は $f(x)=0$ とする）。スコアは $f(1),f(2),\dots,f(N)$ の最小値である。
スコアのとり得る最大値を求めてください。
制約
- $1\leq N\leq 10^9$
- $1\leq M\leq 10^5$
- $1\leq X_i\leq N$
- $1\leq Y_i\leq 10^9$
- 入力は全て整数である
入力
入力は標準入力から以下の形式で与えられる。
$N$ $M$
$X_1$ $Y_1$
$\vdots$
$X_M$ $Y_M$
出力
求める値を一行で出力せよ。
入力例 1
4 4
3 8
1 9
2 7
1 7
出力例 1
7
次のように操作すればスコア $7$ を達成できます。
- $1$ 番目のコマを $(3,8)\to(4,7)$ と動かす。
- $2$ 番目のコマを $(1,9)\to(2,8)\to(3,7)$ と動かす。
- $3,4$ 番目のコマは動かさない。
入力例 2
100 4
2 7
1 8
2 8
1 8
出力例 2
0
同じマスに $2$ 個以上のコマが置かれている場合もあります。
入力例 3
9 10
3 1415
9 2653
5 8979
3 2384
6 2643
3 8327
9 5028
8 4197
1 6939
9 3751
出力例 3
2384