봅슬레이

베시(Bessie)가 봅슬레이 대회에 참가했습니다. 코스의 길이는 $L$미터입니다 ($2 \le L \le 1{,}000{,}000{,}000$).

베시는 출발선에서 초속 $1$미터로 출발합니다. 이후 이동하는 매 $1$미터의 중간 지점 부근에서, 그녀는 다음 세 가지 중 하나로 속도를 조절할 수 있습니다: 중력을 이용해 속도를 $1\,\text{m/s}$ 높이거나, 속도를 그대로 유지하거나, 제동을 걸어 속도를 $1\,\text{m/s}$ 낮춥니다. 따라서 어떤 $1$미터 구간을 시작할 때의 속도와, 바로 다음 $1$미터 구간을 시작할 때의 속도의 차이는 최대 $1$입니다.

코스에는 $N$개의 커브가 있습니다 ($1 \le N \le 100{,}000$). $i$번째 커브는 출발점에서 $T_i$미터 지점에 있으며 ($1 \le T_i \le L-1$), 베시는 그 지점(미터 눈금 $T_i$)에 진입하는 순간의 속도가 $S_i\,\text{m/s}$ 이하여야 합니다 ($1 \le S_i \le 1{,}000{,}000{,}000$). 결승선은 어떤 속도로 통과해도 됩니다.

출발선과 결승선 사이(양 끝 포함)에서 베시가 낼 수 있는 가장 빠른 속도를 구하세요.

여기서 "미터 눈금 $k$에서의 속도"란 $k$미터 지점을 지나는 순간, 즉 $(k+1)$번째 미터를 달리기 시작할 때의 속도를 뜻합니다. 미터 눈금 $0$에서의 속도는 항상 $1$입니다.

아래는 코스를 나타낸 그림입니다. 정수는 미터 눈금이고, 대괄호 안의 수는 해당 커브의 제한 속도입니다 (예: [3]).

|   1   2   3   4   5   6   7[3]
|---+---+---+---+---+---+---+
|                            \
Start                         + 8
                               \
                                + 9
                                 \
                                  + 10       +++ 14 (finish)
                                   \         /
                              11[1] +---+---+
                                        12  13[8]

아래 표는 위 코스에서 각 미터 눈금을 지날 때의 베시의 속도를 나타냅니다.

Max:                              3               1       8
Mtrs: 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
Spd:  1   2   3   4   5   5   4   3   4   3   2   1   2   3   4

이 경우 베시의 최고 속도는 미터 눈금 $4$ 부근에서의 $5$입니다.

• 첫째 줄: 공백으로 구분된 두 정수 $L$과 $N$.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$번째 줄에는 $i$번째 커브를 나타내는 두 정수 $T_i$와 $S_i$가 공백으로 구분되어 주어집니다.

• 한 줄에 정수 하나: 출발선부터 결승선까지(양 끝 포함) 베시가 도달할 수 있는 최대 속도.