- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
«مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا...
به تازگی پلیس با خبر شده که قرار است حمله‌ای تروریستی به شهر بشود. فعلا تروریست‌ها در خانه‌هایی در کنار خیابان آزادی پنهان شده‌اند. در کنار خیابان آزادی $n$ خانه وجود دارد و در هر خانه حداکثر یک تروریست زندگی می‌کند.
برای مهار این حمله‌ی تروریستی و دستگیری تروریست‌ها، $m$ پلیس آن خانه‌ها را زیر نظر گرفته‌اند. پلیس $i$-ام خانه‌های $l_i$ تا $r_i$ را زیر نظر گرفته‌است. می‌دانیم اگر در بازه‌ی تحت نظر یک پلیس بیش از یک تروریست زندگی کند، پلیس‌ها مشکوک شده و تروریست‌ها را دستگیر می‌کنند.
مسریکس که از این ماجرا خبردار شده است، با خودش فکر می‌کند شاید بیشینه‌ی تعداد تروریست‌هایی که در این خانه‌ها می‌توانند زندگی کنند(بدون آن که دستگیر شوند) می‌تواند پارامتری موثّر در بحران محیط زیست باشد. پس از شما می‌خواهد که این مقدار را برای او محاسبه کنید.
ورودی
در سطر اوّل ورودی به ترتیب دو عدد $n$ و $m$ می‌آید.
در سطر $i$-ام از $m$ سطر بعد، دو عدد $l_i$ و $r_i$ آمده‌است که نشان‌دهنده‌ی بازه‌ی خانه‌هایی است که پلیس $i$-ام زیر نظر گرفته است.
$$1 \le l_i \le r_i \le n$$ $$1 \le n, m \le 100\ 000$$
خروجی
در تنها سطر خروجی حداکثر تعداد تروریست‌هایی را چاپ کنید که می‌توانند در این خانه‌ها زندگی کنند و دستگیر نشوند.
مثال
ورودی نمونه ۱
5 2
1 3
2 4
خروجی نمونه ۱
3
ورودی نمونه ۲
6 3
2 4
3 5
2 5
خروجی نمونه ۲
3
ارسال پاسخ برای این سؤال