问题描述

民间有一种烟花棒，点燃时，明艳的火星划过空中，点点闪烁，宛如漫天繁星。

小鱼获得了一根长度为 $n$ 的烟花棒，对烟花充满好奇的小羊会在若干时刻用打火机尝试点燃烟花棒的某一位置（烟花棒一共有 $n$ 个位置，从左往右编号为 $1$ 到 $n$。一开始，$n$ 个位置都未被燃尽）。

具体为 $m$ 次操作，第 $i$ 次操作：在第 $t_i$ 秒初点燃烟花棒的 $x_i$ 位置。

注意：

1. 当第 $x_i$ 位置在 $t_i$ 秒初被点燃时，第 $t_i$ 秒末 $x_i$ 位置被燃尽。然后第 $t_{i+1}$ 秒初火花传递到 $x_{i-1}$ 与 $x_{i+1}$ 位置上，第 $t_{i+1}$ 秒末 $x_{i-1}$ 与 $x_{i+1}$ 位置被燃尽，以此类推。
2. 若小羊在 $t_i$ 秒初点燃了一个被燃尽的位置，则烟花棒不会发生变化。
3. 在同一时刻可能会点燃多个位置，同一位置也可能在多个不同时刻被点燃。

小鱼想知道烟花棒被燃尽的最小时刻。

输入格式

第一行包含两个正整数 n，m，表示烟花棒长度为 n，有 m 次操作。

随后 $m$ 行，每行输入两个正整数 $t_i$，$x_i$，表示第 $i$ 次操作发生在第 $t_i$ 秒初，尝试点燃的位置为 $x_i$。

输出格式

输出一个正整数，表示烟花棒燃尽的最短时间。

样例输入1

3 1
1 2

样例输出1

2

样例输入2

8 4
1 3
2 7
4 4 
4 5

样例输出2

3

评测数据规模

$1\leq n \leq10^5$

$1 \leq m \leq10^5$

$1\leq t_i \leq10^9$

$1\leq x_i \leq n$