[USACO09DEC] Bobsledding S

题目描述

Bessie 参加了一场雪车比赛。赛道总长度为 $L$ 米。

Bessie 从起点出发时的速度为 $1$ 米/秒。在赛道上每前进 $1$ 米，她都可以选择：

• 加速 $1$ 米/秒；
• 保持当前速度；
• 减速 $1$ 米/秒。

也就是说，如果 Bessie 在位置 $x$ 处的速度为 $v$，那么到达位置 $x+1$ 时的速度可以是 $v-1$、$v$ 或 $v+1$。

赛道上有 $N$ 个转弯。第 $i$ 个转弯位于距离起点 $T_i$ 米的位置，为了安全，Bessie 到达这个位置时的速度不能超过 $S_i$ 米/秒。

Bessie 到达终点时没有速度限制。

请计算：在满足所有转弯速度限制的前提下，Bessie 在从起点到终点的整个过程中能够达到的最大速度是多少。

输入格式

第一行包含两个整数 $L,N$，分别表示赛道长度和转弯数量。

接下来 $N$ 行，每行包含两个整数 $T_i,S_i$，表示第 $i$ 个转弯的位置及该位置的最大允许速度。

输出格式

输出一行一个整数，表示 Bessie 在整个比赛过程中能够达到的最大速度。

样例输入

14 3
7 3
11 1
13 8

样例输出

5

样例解释

转弯限制分别为：

• 位置 $7$：速度不能超过 $3$；
• 位置 $11$：速度不能超过 $1$；
• 位置 $13$：速度不能超过 $8$。

一种最优的速度变化方案如下：

位置：0  1  2  3  4  5  6  7  8  9  10 11 12 13 14
速度：1  2  3  4  5  5  4  3  4  3   2  1  2  3  4

因此 Bessie 能达到的最大速度为 $5$。

数据范围

对于所有数据：

• $2\le L\le 10^9$；
• $1\le N\le 10^5$；
• $1\le T_i\le L-1$；
• $1\le S_i\le 10^9$。