ساعت
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
ساعت
دقیقه
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
دقیقه
ثانیه
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
ثانیه
  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

در محیط آزمایشی یونیا زمان به بازه‌های یک دقیقه‌ای تقسیم شده است. به عبارت دیگر به ازای هر i صحیح نامنفی، بازه‌ی [i,i+1)[i,i+1) بازه‌ی زمانی ii را نشان می‌دهد. کوزت در صورتی فردی را ملاقات می‌کند که در طی یک بازه‌ی زمانی با او در یک واگن باشد. در طی آزمایش، اگر تعداد واگن‌های قطار nn باشد، افراد در mm گروه nn نفره وارد قطار می‌شوند. افراد گروه ii ام همه در ابتدای بازه‌ی زمانی lil_i وارد قطار شده و هر یک به یک واگن جداگانه می‌روند و سپس در ابتدای بازه‌ی زمانی rir_i همه از قطار خارج می‌شوند. به طور دقیق‌تر افراد گروه iiام در بازه‌های زمانی lil_i تا ri1r_i-1 (شامل هر دو) داخل قطار هستند. کوزت در بازه‌ی زمانی صفر بر اساس بهترین استراتژی ممکن با هدف ملاقات همه‌ی افراد و با دانستن زمان ورود و خروج گروه‌ها، وارد یکی از واگن‌های قطار می‌شود و پس از آن در ابتدای هر بازه‌ی زمانی می‌تواند یا در واگن فعلی بماند و یا به یکی از واگن‌(های) مجاور برود.

لازم به ذکر است که اگر واگن‌های قطار را از چپ به راست با اعداد 1 تا nn شماره‌گذاری کنیم، واگن aa و bb باهم مجاورند اگر و فقط اگر ab=1|a-b|=1.

کوزت می‌خواهد بداند بیشترین تعداد واگن‌ برای این قطار، که او بتواند در محیط آزمایشی یونیا همه‌ی افرادی که وارد مترو می‌شوند را حداقل یک‌بار ملاقات کند چقدر است؟

ورودی

در خط اول ورودی عدد طبیعی mm تعداد گروه ها در محیط آزمایشی یونیا آمده است. در هر یک از mm خط بعدی به ترتیب دو عدد lil_i و rir_i آمده است که شماره‌ی بازه‌ی زمانی ورود و خروج گروه iiام در محیط آزمایشی یونیا است.

1m500 0001 \leq m \leq 500\ 000 0ri1090 \leq r_i \leq 10^9

خروجی

در تنها خط خروجی، جواب مسئله را چاپ کنید.

زیرمسئله‌ها

زیرمسئله نمره محدودیت
۱ ۱۲ m,li,ri500 m,l_i,r_i \le 500
۲ ۲۷ m2 000 m \le 2\ 000
۳ ۳۲ m50 000 m \le 50\ 000
۴ ۱۹ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

2
3 7
6 10
Plain text

خروجی نمونه ۱

4
Plain text

ورودی نمونه ۲

2
3 8
1 10
Plain text

خروجی نمونه ۲

5
Plain text

۲۵امین دوره المپیاد کامپیوتر - آزمون عملی نهایی دوم - ۱۳۹۴/۶/۲۱


ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.