+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- جمشید کاظمی (که با نام مستعار کامران پوریایی شناخته می‌شود)، به تازگی آدم شده و از زندان آزاد شده است. جمشید پس از حل معمای بزرگ اسنپ؛ طی ۷۰ روز، خودش را با تکنولوژی‌های روز برنامه‌نویسی آشنا کرد و به سرعت به علت استعدادهای بالایش به عضوی ارشد در اسنپ تبدیل شد. اسنپ می‌خواهد به زودی از سرویس ویژه‌ی خود به نام *اسنپ لوکس* در *خیابان بورس* رونمایی کند. آنها قبل از رونمایی باید مسئله‌ی بزرگی را حل کنند و حل این مسئله را به جمشید سپرده‌اند. *خیابان بورس*، مرکز بورس ایران، خیابانی طویل و **افقی** است که در یک طرف آن می‌توان ماشین را متوقف نمود. محل پارک توسط شهرداری خط‌کشی شده‌است و کنار این خیابان به ترتیب و پشت سر هم $m+1$ جایگاهِ برای توقف و پارک ماشین وجود دارد که با ۰ تا $m$ از چپ به راست شماره‌گذاری شده‌است. برای پارک کردن در برخی از جایگاه‌های پارک ماشین، باید ماشین مورد نظر برچسب الکترونیکی *الکتروپارک* داشته باشد که خیلی خیلی گران‌قیمت است. از آنجا که طول خیابان زیاد است شهرداری این جایگاه‌ها را با $n$ بازه‌ی بدون اشتراک مشخص کرده‌است. بازه $i$ ام بیانگر این است که تمامی جایگاه‌های پارک با شماره بین $l_i$ و $r_i$ (**شامل هردو**)‌ نیاز به برچسب *الکتروپارک* دارند. آنها می‌خواهند برای ارائه سرویس بهینه به مردم، ماشین‌های لوکس خود را در این خیابان به صورت آماده‌باش در برخی از این جایگاه‌ها پارک کند. اسنپ در حال حاضر دو ماشین لوکس خود را در جایگاه ۰ و $m$ قرار داده‌است. برای اینکه مردم بتوانند سریع به ماشین خود برسند، هیچ دو ماشین لوکس مجاوری **نباید** فاصله‌ای بیشتر از ‌$k$ داشته باشند (به عبارتی دیگر در هر $k$ جایگاه پارک متوالی، باید حداقل یک ماشین لوکس وجود داشته باشد). بنابراین ممکن است نیاز داشته باشند ماشین‌های لوکسی در میان این دو جایگاه قرار دهند؛ از این رو اسنپ برای برآورده کردن نیاز مشتری در ابتدا می‌خواهد کمترین تعداد ماشین لوکس را در جایگاه‌های نیازمند *الکتروپارک* قرار دهد و سپس در بین همه‌ی روش‌های موجود قرار دادن ماشین‌ها با کمترین ماشین در جایگاه نیازمند *الکتروپارک*، مجموعاً از کمترین تعداد ماشین لوکس استفاده کند. به جمشید کمک کنید تا این مسئله را حل کند تا خودش را به لیدر تیم خود ثابت کند. # ورودی در سطر اول ورودی، سه عدد صحیح $n$ و $m$ و $k$ آمده‌است. سپس در سطر $i$ از $n$ سطر بعدی به ترتیب دو عدد صحیح $l_i$ و $r_i$ آمده‌است. بازه‌ها در ورودی به صورت صعودی آمده‌اند؛ یعنی $r_i < l_{i+1}$. تضمین می‌شود هیچ دو بازه‌ای اشتراک ندارند و هیچ کدام شامل جایگاه ۰ و $m$ نیستند. $$1 \le n \le 100\ 000$$ $$1 \le k \le m \le 10^9$$ $$1 \le l_i \le r_i \le m - 1$$ # خروجی در تنها سطر خروجی، دو عدد چاپ کنید. عدد اول کمترین تعداد ماشین لوکس که نیازمند الکتروپارک هستند و عدد دوم کمترین تعداد ماشین لوکس مورد نیاز برای اضافه شدن است. (بجز ماشین‌هایی که در جای پارک ۰ و $m$ قرار گرفته‌اند.) # مثال ## ورودی نمونه ۱ ``` 2 9 2 3 5 8 8 ``` ## خروجی نمونه ۱ ``` 1 4 ``` در پاسخ بهینه برای این نمونه ماشین‌ها در محل‌های پارک ۲، ۴، ۶ و ۷ اضافه می‌شوند که جایگاه شماره ۴ نیاز به برچسب الکتروپارک دارد. ## ورودی نمونه ۲ ``` 2 6 3 1 2 3 4 ``` ## خروجی نمونه ۲ ``` 1 1 ``` در این نمونه بهترین حالت این است که یک ماشین در محل پارک ۳ اضافه شود که نیاز به برچسب الکتروپارک هم دارد.

حل سؤال در بانک سؤالات