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