مسابقه تمرینی برنامه نویسی جمعی از دانشجویان پیام نور هشتگرد

مارپله‌ی ایرانی


در پی بومی‌سازی مار و پله به بازی زیر دست یافتیم:

مهره‌ای داریم روی نقطه‌ي صفر محور یک بعدی مختصات. این مهره تنها به سمت راست حرکت می‌کند. هم‌چنین در این بازی به جای مار و پله آیتم جدید به نام ماپله داریم. ماپله‌ها به این صورت هستند که دو سر دارند. یکی در خانه‌ی xx و دیگری در yy و هرگاه مهره‌ی ما به یکی از دو سر ماپله برسد از سمت دیگر ماپله ظاهر می‌شود. به ازای هر بار که مهره‌ی ما در دام یک ماپله بیفتد باید یک ریال جریمه بپردازیم. بازی هنگامی تمام می‌شود که مهره‌ی ما به سمت راست سمت راست‌ترین ماپله برسد در واقع در سمت راست آن دیگر سر هیچ ماپله‌ای نباشد. هم‌چنین nn ماپله‌ی اولیه بر روی محور مختصات موجود است . شما باید مکان mm ماپله‌ی جدید را طوری تعیین کنید که جریمه‌ی پرداختی توسط ما بیشینه شود. مختصات ماپله‌های جدیدی می‌تواند هر مقداری باشد و لزومی ندارد که اعداد صحیح باشد ولی ماپله‌های ابتدایی همگی روی نقاط صحیح قرار دارند. هم‌چنین دو سر ماپله نمی‌تواند روی هم بیفتد.

راهنمایی : ماپله‌ها هر طور که قرار گرفته باشند مهره‌ي ما به صورت یکتا حتما به سمت راست آخرین ماپله خواهد رسید.

ورودی🔗

  • در سطر اول ورودی عدد nn آمده است.
  • در سطر دوم ورودی عدد mm آمده است.
  • و در nn سطر بعدی، در هر سطر آن دو عدد آمده که نشانگر دو سر یک ماپله است.

خروجی🔗

در تنها سطر خروجی بیشینه مقدار جریمه‌ای که باید بپردازیم را بنویسید.

محدودیت‌ها🔗

  • همیشه 1n1051 \leq n \leq 10^5
  • همیشه 1m1061 \leq m \leq 10^6
  • همچنین تمامی مختصات‌ها بین ۱ تا 2×1062 \times 10^6‌ هستند.

مثال🔗

ورودی نمونه ۱

3
1
10 11
1 4
2 3
Plain text

خروجی نمونه ۱

6
Plain text

ورودی نمونه ۲

3
3
5 7
6 10
1999999 2000000
Plain text

خروجی نمونه ۲

12
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.