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

---

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

در محیط آزمایشی یونیا زمان به بازه‌های یک دقیقه‌ای تقسیم شده است. به عبارت دیگر به ازای هر i صحیح نامنفی، بازه‌ی \([i,i+1)\) بازه‌ی زمانی \(i\) را نشان می‌دهد. کوزت در صورتی فردی را ملاقات می‌کند که در طی یک بازه‌ی زمانی با او در یک واگن باشد. در طی آزمایش، اگر تعداد واگن‌های قطار \(n\) باشد، افراد در \(m\) گروه \(n\) نفره وارد قطار می‌شوند. افراد گروه \(i\) ام همه در ابتدای بازه‌ی زمانی \(l_i\) وارد قطار شده و هر یک به یک واگن جداگانه می‌روند و سپس در ابتدای بازه‌ی زمانی \(r_i\) همه از قطار خارج می‌شوند. به طور دقیق‌تر افراد گروه \(i\)ام در بازه‌های زمانی \(l_i\) تا \(r_i-1\) (شامل هر دو) داخل قطار هستند. کوزت در بازه‌ی زمانی صفر بر اساس بهترین استراتژی ممکن با هدف ملاقات همه‌ی افراد و با دانستن زمان ورود و خروج گروه‌ها، وارد یکی از واگن‌های قطار می‌شود و پس از آن در ابتدای هر بازه‌ی زمانی می‌تواند یا در واگن فعلی بماند و یا به یکی از واگن‌(های) مجاور برود.

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

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

ورودی

در خط اول ورودی عدد طبیعی \(m\) تعداد گروه ها در محیط آزمایشی یونیا آمده است. در هر یک از \(m\) خط بعدی به ترتیب دو عدد \(l_i\) و \(r_i\) آمده است که شماره‌ی بازه‌ی زمانی ورود و خروج گروه \(i\)ام در محیط آزمایشی یونیا است.

\[1 \leq m \leq 500\ 000\] \[0 \leq r_i \leq 10^9\]

خروجی

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

زیرمسئله‌ها

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

مثال

ورودی نمونه ۱

2
3 7
6 10

خروجی نمونه ۱

4

ورودی نمونه ۲

2
3 8
1 10

خروجی نمونه ۲

5

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