- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
هنرمند وسواسی $n$ ستون ساخته و آن‌ها را برای نمایش در یک گالری هنری نصب کرده است. این ستون‌ها در یک ردیف و به صورت متوالی نصب شده‌اند. هنرمند پس از نصب ستون‌ها متوجه شده است که این ستون‌ها خوش ترتیب نیستند. تعدادی ستون که در یک ردیف نصب شده‌اند، خوش ترتیب‌اند اگر و تنها اگر ارتفاع هر دو ستون مجاور متفاوت باشد.
متاسفانه هنرمند وسواسی امکان تغییر ترتیب ستون‌ها یا کاهش ارتفاع آن‌ها را ندارد. برای هر ستون او تنها می‌تواند ارتفاع ستون را تغییر ندهد و یا ارتفاع آن را مقدار صحیحی افزایش دهد. دقت کنید که مواد به کار رفته در ساخت ستون ها متفاوت است، به همین دلیل افزایش یک واحد ارتفاع هر ستون، هزینه‌ای دارد که مخصوص آن ستون است. هنرمند وسواسی می‌خواهد با افزایش ارتفاع تعدادی از این ستون‌ها، آن‌ها را خوش ترتیب کند و از ما کمک خواسته است تا به او بگوییم کم‌ترین هزینه برای انجام این کار چقدر است.
ورودی
در خط اول ورودی $n$، تعداد ستون‌ها، داده می‌شود. در $n$ خط بعدی، اطلاعات مربوط به ستون‌ها، به ترتیب داده می‌شود. در خط $i$ام، به ترتیب اعداد صحیح $a_i$ و $b_i$ داده می‌شوند که به ترتیب ارتفاع ستون $i$ام و هزینه‌ی افزایش یک واحد آن هستند.
$$1 \leq n \leq 10^5$$ $$1 \leq a_i, b_i \leq 10^4$$
خروجی
در خروجی کم‌ترین هزینه‌ی ممکن برای خوش ترتیب کردن ستون‌ها را چاپ کنید.
مثال‌ها
ورودی نمونه ۱
6
2 5
3 4
3 20
3 3
4 2
6 10
خروجی نمونه ۱
9
در مثال بالا برای کم‌ترین هزینه باید به ارتفاع ستون‌های دوم، چهارم و پنجم یک واحد افزوده شود.
ورودی نمونه ۲
3
11 10
10 4
10 10
خروجی نمونه ۲
8
در مثال بالا برای کم ترین هزینه باید ارتفاع ستون دوم، دو واحد افزایش یابد.
ارسال پاسخ برای این سؤال