Bessie thi xe trượt tuyết, hy vọng cân nặng lớn lợi thế trên $L$ mét ($2 \le L \le 1,000,000,000$).

Xuất phát $1$ mét/giây, có thể đổi tốc độ. Gần giữa mỗi mét tăng bằng trọng lực $1$ mét/giây hoặc phanh giữ nguyên hay giảm $1$ mét/giây.

Xuống dốc có $N$ ($1 \le N \le 100,000$) khúc cua. Cua $i$ cách đầu $T_{i}$ mét ($1 \le T_{i} \le L-1$); khi vào mét ấy tốc độ không quá $S_{i}$ mét/giây ($1 \le S_{i} \le 1,000,000,000$). Qua đích tốc độ bất kỳ.

Tìm tốc độ cao nhất có thể mà không vượt giới hạn cua.

Số nguyên là vạch mét, ngoặc là giới hạn như $[3]$:

|   1   2   3   4   5   6   7[3]
|---+---+---+---+---+---+---+
|                            \
Xuất phát                         + 8    
                               \
                                + 9    
                                 \
                                  + 10       +++ 14 (đích)
                                   \         /
                              11[1] +---+---+
                                        12  13[8]

Bảng dưới là tốc độ đầu mỗi mét:

Cao nhất $5$ gần đầu mét $4$.

Dữ liệu vào

• Dòng $1$: số nguyên $L$, $N$ cách bởi dấu cách.

• Dòng $2..N+1$: dòng $i+1$ mô tả cua $i$ bằng số nguyên $T_{i}$, $S_{i}$ cách bởi dấu cách.

Dữ liệu ra

• Dòng $1$: số nguyên, tốc độ cao nhất giữa đầu và đích, gồm cả hai.

Ví dụ

Dữ liệu vào 1

14 3
7 3
11 1
13 8

Dữ liệu ra 1

5

Tác giả bài toán: Brian Jacokes, 2009