رستوران‌داری


  • محدودیت زمان: ۱.۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

رضا یک رستوران تاسیس کرده که در طبقه‌ی آخر ساختمانی ضد زلزله قرار دارد. در صورت وقوع زلزله، ساختمان به چپ متمایل می‌شود رضا nn میز در رستوان دارد که میز ii ام در فاصله did_i متری درب ورودی قرار دارد (توجه کنید did_i می‌تواند منفی یا مثبت باشد؛ منفی یعنی میز سمت چپ و مثبت یعنی میز سمت راست درب قرار دارد).

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

رضا به شاگردش پول می‌دهد تا کارها را انجام دهد. شاگرد به ازای هر یک متری که میزی را هل دهد، هزار تومان می‌گیرد. پول چسباندن میز ii ام به زمین، tit_i هزار تومان است. (که می‌تواند مثبت یا منفی باشد، در صورتی که tit_i منفی باشد، رضا از شاگردش بابت چسباندن میز پول می‌گیرد!)

شما باید برنامه‌ای بنویسید که در صورت وقوع زلزله، کمترین هزینه‌ی ممکن برای چسباندن و هل دادن میزها را حساب کند.

توجه داشته باشید نباید میزی از پنجره بیرون بیفتد وگرنه رستوران بسته و رضا ورشکسته می‌شود.

ورودی🔗

در اولین خط عدد nn یعنی تعداد میزها آمده است. 1n2 8001 \le n \le 2\ 800 در خط دوم، nn عدد می‌آید که did_i ها هستند. تضمین می‌شود هیچ دو میزی در ابتدا در یک نقطه قرار ندارند. (didj)(d_i \neq d_j)

در نهایت در خط سوم، nn عدد می‌آید که tit_i ها هستند.

230di,ti230-2^{30} \leq d_i, t_i \leq 2^{30}

خروجی🔗

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

مثال🔗

ورودی نمونه ۱🔗

3
0 2 10
5 6 13
Plain text

خروجی نمونه ۱🔗

17
Plain text

کافیست تنها چپ‌ترین میز چسبانده شود. در اینصورت ۵ هزار تومان هزینه‌ی چسباندن آن است و دو میز دیگر به سمت آن می‌لغزند و هزینه‌ی هل دادن آن‌ها به جایگاه اولشان، ۱۰ + ۲ = ۱۲ هزار تومان است و جمعا ۱۷ هزار تومان هزینه می‌کنیم.

ورودی نمونه ۲🔗

4
-4 -3 14 -1
100 -4 1 0
Plain text

خروجی نمونه ۲🔗

97
Plain text

در این مثال بهتر است همه‌ی میزها را به زمین بچسبانیم و در مجموع ۹۷ هزار تومان خرج می‌کنیم.

ورودی نمونه ۳🔗

4
6 2 5 3
1 7 100 2
Plain text

خروجی نمونه ۳🔗

12
Plain text

میز دوم باید چسبانده شود تا از پنجره بیرون نیفتد. اگر میز اول و دوم و چهارم را بچسبانیم ۱۰ هزار تومان هزینه می‌دهیم. ۲ هزار تومان هم هزینه‌ی هل دادن میز سوم است و در مجموع ۱۲ هزار تومان هزینه می‌کنیم.

ورودی نمونه ۴🔗

5
1 2 3 4 5
3 3 3 3 3
Plain text

خروجی نمونه ۴🔗

10
Plain text

بهترین جواب، چسباندن میز اول و چهارم است که باعث می‌شود سه میز دیگر لیز بخورند و هزینه‌ی هل دادن آن‌ها، ۴ هزار تومان و هزینه‌ی کل، ۱۰ هزار تومان شود.