Oil well

برادران دالتون پس از فرار از زندان برای تامین مخارج روزمره‌ی زندگی به استخراج از چاه‌های نفت دوبعدی روآورده اند. (دقت کنید که انیمیشن لوک خوش‌شانس یک انیمیشن دوبعدی است.) یک چاه نفت دوبعدی به شکل یک جدول نامتناهی با $n$ ستون و $10^9$ سطر است که در بالای سطر اول آن، سطح زمین قرار گرفته است. هر ستون از میزان‌های مشخصی از خاک، نفت و سنگ تشکیل شده است. بر اساس نحوه‌ی به وجود آمدن نفت طی مرور زمان، در هر ستون از چاه نفت، در یک بازه‌ی صحیحی از عمق زمین نفت وجود دارد که این بازه را برای ستون $i$ام با $[l_i, r_i]$ نشان می‌دهیم و به این معناست که از عمق $l_i$ تا عمق $r_i$ از ستون $i$ام از نفت تشکیل شده است. درنتیجه این ستون شامل $r_i - l_i$ واحد نفت است. هم‌چنین می‌دانیم که همواره از سطح زمین تا عمق شروع نفت، یعنی بازه‌ی $[0, l_i]$، از خاک تشکیل شده، و از عمق پایان نفت تا انتهای چاه نفت، یعنی بازه‌ی $[r_i, 10^9]$، از سنگ تشکیل شده است. برای مثال، اگر بازه‌ی نفت در یک ستون $[1,3]$ باشد، در آن ستون، ۱ واحد خاک و ۲ واحد نفت موجود است.

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

پس از کندن یک زیرمستطیل از چاه نفت، برادران دالتون می‌توانند از تمامی منافذی که به ذخایر نفت متصل است، با استفاده از دستگاه نفت‌کِش، نفت استخراج کنند. دقت‌کنید که منظور از منافذ تمام درایه‌هایی شامل نفت از ماتریس است که پس از کَندن زیرمستطیل در معرض هوا قرار گرفته اند. به عبارت دیگر، تمام درایه‌های موجود در جدول که یکی از درایه‌های مجاور (منظور از مجاورت در این سوال، مجاورت ضلعی است. به این معنی که دو درایه ضلع مشترک داشته باشند.) آن‌ها درون ‌زیرمستطیل کنده شده قرار داشته است. دستگاه نفت‌کِش پس از اتصال به یک منفذ، تمامی واحد‌های نفت که با مسیری از درایه‌های شامل نفت به منفذ می‌رسد را می‌مکد و از خروجی بیرون می‌دهد تا برادران دالتون آن‌ها را جمع آوری کنند. یک درایه‌ی شامل نفت به یک منفذ مسیر دارد، اگر دنباله‌ای از درایه‌های شامل نفت با شروع از آن خانه و پایان در منفذ موجود باشد که هر دو عضو متوالی در دنباله مجاور باشند.

حداکثر مقدار نفتی که برادران دالتون می‌توانند جمع کنند چقدر است؟

در خط اول ورودی $n$، تعداد ستون‌های چاه نفت آمده است.

در $n$ خط بعدی ورودی،‌ در هر خط دو عدد طبیعی $l_i$ و $r_i$ آمده است که شروع و پایان بازه‌ی تشکیل شده از نفت در ستون $i$ام را نشان می‌دهند.

در تنها خط خروجی، حداکثر مقدار نفتی که برادران دالتون می‌توانند جمع کنند را چاپ کنید.

• زیرمسئله اول (۱ نمره): نفت نداریم ($l_i = r_i$)
• زیرمسئله دوم (۲ نمره): سنگ نداریم ($r_i = 10^9$)
• زیرمسئله سوم (۳ نمره): خاک نداریم ($l_i = 1$)
• زیرمسئله چهارم(۱۲ نمره): $n \le 20$
• زیرمسئله پنجم(۲۱ نمره): $n \le 2000$
• زیرمسئله ششم(۶۱ نمره): بدون محدودیت اضافی

دقت کنید همواره یک لایه خاک بر روی چاه نفت وجود دارد و در زیرمساله‌ی سوم منظور بدون درنظر گرفتن آن لایه است.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le n \le 2 \times 10^5$
• $1 \le l_i \le r_i \le 10^9$

ورودی نمونه همان شکل صفحه‌ی اول سوال است و خط ‌چین قرمز زیرمستطیلی که نفت‌کَن می‌کَند را نشان می‌دهد.

• سوال بعد
• سوال قبل