پنجره‌ی کثیف


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

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

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

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

ورودی🔗

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

در خط ii ام از kk خط بعدی دو عدد xix_i و yiy_i آمده که به ترتیب نشانگر شماره ردیف و ستون لکه‌ی ii اُم است. 2n100 0002 \le n \le 100\ 000 1kmin(300000,n×n)1 \le k\,\leq\,\min\left(300\,000,\,n\times n\right) 1xi,yin1 \le x_i, y_i \le n

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

خروجی🔗

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

مثال🔗

ورودی نمونه ۱🔗

5 6
1 1
1 3
2 2
2 4
3 5
4 5
Plain text

خروجی نمونه ۱🔗

3
Plain text

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

توضیح تصویر

ورودی نمونه ۲🔗

4 7
1 1
1 2
2 2
2 4
3 3
4 1
4 2
Plain text

خروجی نمونه ۲🔗

3
Plain text

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

توضیح تصویر