+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- رضا یک رستوران تاسیس کرده که در طبقه‌ی آخر ساختمانی ضد زلزله قرار دارد. در صورت وقوع زلزله، ساختمان به چپ متمایل می‌شود رضا $n$ میز در رستوان دارد که میز $i$ ام در فاصله $d_i$ متری درب ورودی قرار دارد (توجه کنید $d_i$ می‌تواند منفی یا مثبت باشد؛ منفی یعنی میز سمت چپ و مثبت یعنی میز سمت راست درب قرار دارد). مدیر ساختمان به رضا هشدار داده اگر ساختمان به چپ متمایل شود، میزها به چپ لیز می‌خورند مگر اینکه آن‌ها را به کف زمین بچسباند. در واقع هر میزی که به زمین چسبیده باشد حرکت نمی‌کند، در غیر این صورت اینقدر به چپ لیز می‌خورد تا به میز سمت چپش برسد (فرض کنید عرض میزها آنقدر کم است که چندین میز می‌تواند در یک فاصله از درب قرار گیرد). همچنین اگر در سمت چپ میزی که به زمین نچسبده، میزی نباشد، از پنجره به بیرون پرت می‌شود و رستوران بسته می‌شود. رضا تصمیم گرفته بعضی میزها را به زمین بچسباند و باقی را بعد از پایان زلزله هل داده و به جای اصلیشان برگرداند. رضا به شاگردش پول می‌دهد تا کارها را انجام دهد. شاگرد به ازای هر یک متری که میزی را هل دهد، هزار تومان می‌گیرد. پول چسباندن میز $i$ ام به زمین، $t_i$ هزار تومان است. (که می‌تواند مثبت یا منفی باشد، در صورتی که $t_i$ منفی باشد، رضا از شاگردش بابت چسباندن میز پول می‌گیرد!) شما باید برنامه‌ای بنویسید که در صورت وقوع زلزله، کمترین هزینه‌ی ممکن برای چسباندن و هل دادن میزها را حساب کند. توجه داشته باشید نباید میزی از پنجره بیرون بیفتد وگرنه رستوران بسته و رضا ورشکسته می‌شود. # ورودی در اولین خط عدد $n$ یعنی تعداد میزها آمده است. $$1 \le n \le 2\ 800$$ در خط دوم، $n$ عدد می‌آید که $d_i$ ها هستند. تضمین می‌شود هیچ دو میزی در ابتدا در یک نقطه قرار ندارند. $$(d_i \neq d_j)$$ در نهایت در خط سوم، $n$ عدد می‌آید که $t_i$ ها هستند. $$-2^{30} \leq d_i, t_i \leq 2^{30}$$ # خروجی در تنها خط خروجی، کمترین هزینه‌ی ممکن برای چسباندن و هل دادن میزها را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 0 2 10 5 6 13 ``` ## خروجی نمونه ۱ ``` 17 ``` کافیست تنها چپ‌ترین میز چسبانده شود. در اینصورت ۵ هزار تومان هزینه‌ی چسباندن آن است و دو میز دیگر به سمت آن می‌لغزند و هزینه‌ی هل دادن آن‌ها به جایگاه اولشان، ۱۰ + ۲ = ۱۲ هزار تومان است و جمعا ۱۷ هزار تومان هزینه می‌کنیم. ## ورودی نمونه ۲ ``` 4 -4 -3 14 -1 100 -4 1 0 ``` ## خروجی نمونه ۲ ``` 97 ``` در این مثال بهتر است همه‌ی میزها را به زمین بچسبانیم و در مجموع ۹۷ هزار تومان خرج می‌کنیم. ## ورودی نمونه ۳ ``` 4 6 2 5 3 1 7 100 2 ``` ## خروجی نمونه ۳ ``` 12 ``` میز دوم باید چسبانده شود تا از پنجره بیرون نیفتد. اگر میز اول و دوم و چهارم را بچسبانیم ۱۰ هزار تومان هزینه می‌دهیم. ۲ هزار تومان هم هزینه‌ی هل دادن میز سوم است و در مجموع ۱۲ هزار تومان هزینه می‌کنیم. ## ورودی نمونه ۴ ``` 5 1 2 3 4 5 3 3 3 3 3 ``` ## خروجی نمونه ۴ ``` 10 ``` بهترین جواب، چسباندن میز اول و چهارم است که باعث می‌شود سه میز دیگر لیز بخورند و هزینه‌ی هل دادن آن‌ها، ۴ هزار تومان و هزینه‌ی کل، ۱۰ هزار تومان شود.

حل سؤال در بانک سؤالات