====== Elephants ======

‎$n$‎ فیل در یک ردیف قرار گرفته‌اند. هر کدام از فیل‌ها یک شماره بین ‎$1$‎ و ‎$n$‎ دارند و شماره تمام فیل‌ها متفاوت است‎.
‎

می‌دانیم در ابتدا فیل شماره ‎$1 \leq a_i \leq n$‎ در مکان ‎$i$‎ام قرار دارد. همچنین وزن فیل شماره ‎$i$‎  برابر با ‎$w_i$‎ است‎.
‎

ما می‌توانیم در هر مرحله دو فیل ‎$i$‎ و ‎$j$‎ را انتخاب کنیم و با پرداخت هزینه ‎$w_i+w_j$‎ مکان دو فیل را عوض کنیم. هدف ما رسیدن به حالتی است که فیل شماره ‎$b_i$‎ در مکان ‎$i$‎ ام قرار داشته باشد. شما باید کم‌ترین هزینه ممکن برای انجام این کار را به دست آورید‎.
‎
===== ورودی =====
  * در سطر اول ورودی عدد ‎$(1 \leq n \leq 10^5)$‎ آمده است‎.‎
  * در سطر بعدی ‎$n$‎ عدد ‎$w_1$‎ تا ‎$w_n$‎ آمده است‎.‎
  * در سطر سوم ‎$n$‎ عدد ‎$a_1$‎ تا ‎$a_n$‎ آمده است‎.‎
  * در سطر چهارم ورودی ‎$n$‎ عدد ‎$b_1$‎ تا ‎$b_n$‎ آمده است‎.
===== خروجی =====


در تنها سطر خروجی پاسخ سؤال را چاپ نمایید‎.

===== محدودیت‌ها =====

  * محدودیت زمان: ۴ ثانیه
  * محدودیت حافظه: ۲۵۶ مگابایت
‎

===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|6‎ \\ ‎2400 2000 1200 2400 1600 4000‎ \\ ‎1 4 5 3 6 2 \\ ‎5 3 2 4 6 1|‎11200‎|

</WRAP>


<پاسخ>
فرض کنید گراف جهت دار ‎$G$‎ گرافی با ‎$n$‎ رأس و ‎$n$‎ یال جهت دار باشد که به ازای هر ‎$i$‎ ، یک یال از ‎$a_i$‎ به ‎$b_i$‎ وجود داشته باشد‎.‎ (به چنین گرافی گراف جایگشت می گویند). چون درجه ورودی و خروجی هر رأس دقیقاً برابر با ‎$1$‎ است، این گراف به تعدادی دور افراز شده است. فرض کنید این دور‌ها ‎$c_1$‎ تا ‎$c_k$‎ باشند‎.

‎
به ازای هر دور ‎$c_i$‎ می‌دانیم که حداقل ‎$|c_i-1|$‎ بار باید فیل‌های متناظر رئوس ‎$c_i$‎ را جابه‌جا کنیم تا تمام فیل‌ها در جای خود قرار بگیرند. اگر بخواهیم با دقیقاً ‎$|c_i-1|$‎ بار جابه جا کردن فیل‌ها این کار را انجام دهیم لزوما تمام جا‌به‌جایی‌ها باید بین فیل‌های همین دور باشد پس حد‌اقل ‎$\sum_{j=1}^{|c_i|}w_{c_{i,j}}‎ + ‎(|c_i|-2) \times \min_{j=1}^{|c_i|}w_{c_{i,j}}$‎ هزینه برای این کار لازم و کافی است‎.

‎
در صورتی که تمام جا‌به‌جایی‌ها بین فیل‌های دور ‎$c_i$‎ نباشد ، بیش‌تر یا مساوی ‎$|c_i|$‎ جا به‌جایی برای این کار لازم است و چون زوجیت تعداد عملیات لازم برای قرار دادن فیل‌ها در جای خود ثابت است ( هر جا‌به‌جایی تعداد دور های گراف جایگشت را یکی کم یا زیاد می کند) پس حداقل ‎$|c_i+1|$‎ جا‌به‌جایی برای این کار لازم است. پس در این صورت حداقل ‎$\sum_{j=1}^{|c_i|}w_{c_{i,j}}‎ + ‎\min_{j=1}^{|c_i|}w_{c_{i,j}}‎ + ‎(|c_i|+1) \times \min_{j=1}^{n}w_j$‎ هزینه برای این کار لازم و کافی است‎.

‎
پس کافیست به ازای هر دور دو مقدار گفته شده را حساب کنیم و مجموع آن‌ها را به عنوان جواب نهایی چاپ کنیم.
</پاسخ>

  * [[سوال ۶۹|سوال بعد]]
  * [[سوال ۶۷|سوال قبل]]