Bessie는 무거운 몸이 $L$미터 코스 ($2 \le L \le 1,000,000,000$)에 유리하길 바라며 봅슬레이에 참가했다.

시작 속도 $1$미터/초이며 변속할 수 있다. 각 미터 중간 근처에서 중력으로 $1$미터/초 가속하거나 브레이크로 유지 또는 $1$미터/초 감속한다.

내리막에 $N$ ($1 \le N \le 100,000$) 굽이가 있다. 굽이 $i$는 출발 후 $T_{i}$미터 ($1 \le T_{i} \le L-1$), 그 미터에 진입할 때 최대 $S_{i}$미터/초 ($1 \le S_{i} \le 1,000,000,000$)다. 도착은 어떤 속도든 가능하다.

굽이 제한을 지키며 도달할 최고 속도를 구하라.

그림의 정수는 미터 표시, 대괄호는 제한으로 예는 $[3]$다:

|   1   2   3   4   5   6   7[3]
|---+---+---+---+---+---+---+
|                            \
출발                         + 8    
                               \
                                + 9    
                                 \
                                  + 10       +++ 14 (도착)
                                   \         /
                              11[1] +---+---+
                                        12  13[8]

표는 각 미터 시작의 속도다:

$4$미터 시작 근처에서 최고 $5$다.

입력

• $1$번째 줄: 공백 구분 정수 $L$, $N$.

• $2..N+1$번째 줄: $i+1$번째 줄은 굽이 $i$를 공백 구분 정수 $T_{i}$, $S_{i}$로 설명한다.

출력

• $1$번째 줄: 출발과 도착 양끝 포함 최고 속도 정수.

예제

입력 1

14 3
7 3
11 1
13 8

출력 1

5

문제 출제: Brian Jacokes, 2009