دخلت 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