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

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

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

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

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

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

• زیرمسئله اول (۱۲ نمره): $m,l_i,r_i\leq 500$
• زیرمسئله دوم (۲۷ نمره): $m\leq 2000$
• زیرمسئله سوم (۳۲ نمره): $m\leq 5\times 10^{4}$
• زیرمسئله چهارم (۲۹ نمره): بدون محدودیت اضافی

• $1 \leq m \leq 5\times 10^5$
• $0 \leq l_i < r_i \leq 10^9$

در ورودی نمونه‌ی اول، گروه اول در ابتدای بازه‌ی $[3, 4)$ وارد قطار می‌شوند و در ابتدای بازه‌ی زمانی $[7, 8)$ از قطار خارج می‌شوند. در نتیجه در چهار بازه‌ی زمانی درون قطار هستند. بنابراین از آن‌جا که کوزت در هر بازه‌ی زمانی حداکثر با یکی از افراد این گروه ملاقات می‌کند طول قطار نمی‌تواند بیشتر از چهار باشد. حال کوزت می‌تواند در بازه‌ی زمانی صفر وارد واگن اول شود و تا بازه‌ی زمانی سوم آن‌جا بماند و از بازه‌ی زمانی چهارم به ترتیب از راست به چپ، در واگن‌های $2$، $3$، $4$، $3$، $2$، $1$ باشد و بنابراین همه‌ی افراد را ملاقات کند.

• سوال قبل