ترور


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

«مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا...

به تازگی پلیس با خبر شده که قرار است حمله‌ای تروریستی به شهر بشود. فعلا تروریست‌ها در خانه‌هایی در کنار خیابان آزادی پنهان شده‌اند. در کنار خیابان آزادی nn خانه وجود دارد و در هر خانه حداکثر یک تروریست زندگی می‌کند.

برای مهار این حمله‌ی تروریستی و دستگیری تروریست‌ها، mm پلیس آن خانه‌ها را زیر نظر گرفته‌اند. پلیس ii-ام خانه‌های lil_i تا rir_i را زیر نظر گرفته‌است. می‌دانیم اگر در بازه‌ی تحت نظر یک پلیس بیش از یک تروریست زندگی کند، پلیس‌ها مشکوک شده و تروریست‌ها را دستگیر می‌کنند.

مسریکس که از این ماجرا خبردار شده است، با خودش فکر می‌کند شاید بیشینه‌ی تعداد تروریست‌هایی که در این خانه‌ها می‌توانند زندگی کنند(بدون آن که دستگیر شوند) می‌تواند پارامتری موثّر در بحران محیط زیست باشد. پس از شما می‌خواهد که این مقدار را برای او محاسبه کنید.

ورودی🔗

در سطر اوّل ورودی به ترتیب دو عدد nn و mm می‌آید.

در سطر ii-ام از mm سطر بعد، دو عدد lil_i و rir_i آمده‌است که نشان‌دهنده‌ی بازه‌ی خانه‌هایی است که پلیس ii-ام زیر نظر گرفته است.

1lirin1 \le l_i \le r_i \le n 1n,m100 0001 \le n, m \le 100\ 000

خروجی🔗

در تنها سطر خروجی حداکثر تعداد تروریست‌هایی را چاپ کنید که می‌توانند در این خانه‌ها زندگی کنند و دستگیر نشوند.

مثال🔗

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

5 2
1 3
2 4
Plain text

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

3
Plain text

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

6 3
2 4
3 5
2 5
Plain text

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

3
Plain text