- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
حسام نگهبان یک ساختمان $n$ طبقه است. طبقات این ساختمان با اعداد $0$ تا $n-1$ شماره‌گذاری شده‌اند. این ساختمان یک آسناسور هم دارد. این آسانسور محدودیتی برای تعداد نفرات ندارد. کلید این آسانسور دست حسام است و تا او وارد نشود هیچ‌کسی نمی‌تواند از این آسانسور استفاده کند.
تا زمانی که حسام به ساختمان برسد $m$ نفر منتظر تشریف فرمایی او هستند، نفر $i$ام می‌خواهد از طبقه‌ی $s_i$ به طبقه‌ی $f_i$ برود.
حسام هم وارد ساختمان شد و دید که آسانسور در طبقه‌ی $0$ است و خودش می‌خواست به طبقه‌ی $n-1$ برود. او می‌خواهد سر راه همه‌ی این $m$ نفر را به مقصد برساند به طوری که مجموع حرکت آسانسور بین طبقات کمینه شود.
توجه کنید حسام ممکن است یک نفر را در یک طبقه‌ای سوار کند و بعد از کلی معطل کردن آن را به طبقه‌ی مورد نظرش برساند و معطل شدن آن فرد اصلاً برای حسام مهم نیست و فقط کمینه حرکت کردن آسانسور مهم است.
زمان توقف آسانسور در طبقات هم مهم نیست و فقط حرکت آسانسور مهم است.
ورودی
در سطر اول ورودی، دو عدد صحیح و مثبت $n$ و $m$ که با یک فاصله از هم جدا شده‌اند آمده که به ترتیب تعداد طبقات ساختمان و تعداد افراد منتظر را نشان می‌دهد. $$2 \leq n \leq 10^9$$ $$1 \leq m \leq 300 , 000$$
در $m$ سطر بعدی، در هر سطر، دو عدد صحیح $s_i$ و $f_i$ آمده که شماره‌ی طبقه‌ای مبدا و مقصد نفر $i$ام را نشان می‌دهد. $$0 \leq s_i \neq f_i \leq n - 1$$
خروجی
در تنها سطر خروجی، تعداد حرکت‌های آسانسور بین طبقات را مشخص کنید.
مثال
ورودی نمونه ۱
10 3
2 9
5 1
7 6
خروجی نمونه ۱
19
ورودی نمونه ۲
7 1
6 0
خروجی نمونه ۲
18
ارسال پاسخ برای این سؤال