• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

عمو اسکروچ که خبر رسیدن قرن جدید را شنیده بود، بالأخره تصمیم گرفت خانه‌ تکانی کند. در میان تمیزکاری‌‌هایش به پنجره‌ای بسیار کثیف برخورد و فهمید در خانه‌اش هیچ شیشه پاک‌کنی ندارد. پس تصمیم به خرید یک شیشه پاک‌کن گرفت.

شیشه‌ی پنجره‌ی خانه عمو اسکروچ به شکل یک جدول $n \times n$ است که در $k$ خانه‌ی آن، یک لکه وجود دارد. ابتدا شیشه پاک‌کن را به صورت افقی در مکانی دلخواه روی ردیف اول شیشه قرار می‌دهیم و سپس در هر مرحله شیشه پاک‌کن را از روی پنجره بلند کرده، آن را یک ردیف پایین آورده، در راستای افقی حداکثر یک واحد جا‌به‌جا کرده و دوباره روی شیشه می‌گذاریم (شیشه‌ پاک‌کن نباید از شیشه بیرون بزند)، در این صورت تمام خانه‌های شیشه که زیر شیشه پاک‌کن هستند تمیز می‌شوند.

از آنجایی که عمو اسکروچ نمی‌خواهد هزینه‌ی زیادی کند، به دنبال کوتاه‌ترین شیشه پاک‌کنی می‌گردد که بتواند تمام $k$ لکه را پاک کند. به او در پیدا کردن طول این شیشه پاک‌کن کمک کنید.

ورودی

در خط اول ورودی دو عدد $n$ و $k$ آمده که به ترتیب نشان دهنده‌ی طول ضلع پنجره و تعداد لکه‌های روی آن است.

در خط $i$ ام از $k$ خط بعدی دو عدد $x_i$ و $y_i$ آمده که به ترتیب نشانگر شماره ردیف و ستون لکه‌ی $i$ اُم است. $$2 \le n \le 100\ 000$$ $$1 \le k,\leq,\min\left(300,000,,n\times n\right)$$ $$1 \le x_i, y_i \le n$$

تضمین می‌شود در هیچ خانه‌ای بیش از یک لکه وجود ندارد.

خروجی

در تنها خط خروجی کمترین طول شیشه پاک‌کن را چاپ کنید.

مثال

ورودی نمونه ۱

5 6
1 1
1 3
2 2
2 4
3 5
4 5

خروجی نمونه ۱

3

با شیشه پاک‌کن به طول کمتر از ۳ نمی‌توان لکه‌ها را پاک کرد. اما با استفاده از شیشه پاک‌کن به طول ۳، می‌توان به صورت زیر شیشه را پاک کرد:

ورودی نمونه ۲

4 7
1 1
1 2
2 2
2 4
3 3
4 1
4 2

خروجی نمونه ۲

3

با شیشه پاک‌کن به طول کمتر از ۳ نمی‌توان لکه‌ها را پاک کرد. اما با استفاده از شیشه پاک‌کن به طول ۳، می‌توان به صورت زیر شیشه را پاک کرد: