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]

Ниже скорости в начале каждого метра:

Максимум $5$ около начала метра $4$.

Входные данные

• Строка $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