TopCoder

User's AC Ratio

93.3% (14/15)

Submission's AC Ratio

26.9% (21/78)

Tags

Description

「阿 ~~~~」妤嬌張了他那大大的嘴巴,準備吃下姐姐第一口餵他吃 的早餐 沒想到就在妤嬌咬下的時候...「咖!」他竟然咬到了自己的牙齒!!
只見姊姊淘氣的拿著湯匙在他面前晃阿晃「顆顆 你還是那麼傻阿 >//////< 妤 嬌 :「 ㄌ ~ ㄩ ~ ㄝ ~ 」
只見妤嬌搖著頭撒嬌道「不管拉 ~ 姐姐你怎麼可以這樣嗎 ~ 人家我不依 ~」 看著傲嬌的妤嬌,姐姐會心的一笑
「好啦 ~ 那...那...因為昨天...你可以再幫我個忙嗎??」 姐姐牽著妤嬌 的手,把妤嬌帶回了他的房間 一進去姐姐就把妤嬌給拉到了床邊......只 見床邊有著一排娃娃,看似由小到大的排列好了...
姐姐對著妤嬌說「雖然看起來是從小到大排好了... 可是... 看起來有點 違和感耶」 「不然...妤嬌你來幫我排成我要的順序好不好>////<
「我們一起排好了之後再一起......吃早餐吧!」 妤嬌想要讓姐姐知道自 己是個可靠的男人,看著姐姐
「沒關係!讓我來就好了!」 妤嬌也只有兩隻手,所以一次只能交換兩 個娃娃。 就在妤嬌要交換前面兩個娃娃的時候,他眉頭一皺,發現事情並 不對勁...... 原來這就是鐵與羽毛的故事嗎?明明大小差不多的娃娃... 卻 不是都一公斤重....... 為了等等要盡情享受與姐姐美味 (?) 的早餐時光,
妤嬌想盡量花費少點力氣將娃娃擺回他該到的位置。 而每搬動兩個娃娃所需要花費的力氣卻是兩個娃娃的質量和! 所以妤嬌想知道最少需要 花費多少力氣才能達到姊姊要求的目標呢?

Input Format

第一行有一個 N,代表共有 N 隻娃娃 (1 ≤ N ≤ 1000000)
第二行有 N 個數字,分別代表第 i 個娃娃的質量 Mi (0 ≤ Mi ≤ 10000)
第三行有 N 個數字,分別代表一開始由左至右的娃娃編號 Pi (1 ≤ Pi ≤ N 且保證不會重複 )
第四行有 N 個數字,分別代表最後由左至右的娃娃編號Qi (1 ≤ Qi ≤ N 且保證不會重複 )

Output Format

請輸出最少需要花費多少力氣?

Sample Input

6
2400 2000 1200 2400 1600 4000
1 4 5 3 6 2
5 3 2 4 6 1

Sample Output

11200

Hints

Problem Source

原TIOJ1785 / problem setter: jeremy89183

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 10000 65536
1 10000 65536
2 10000 65536
3 10000 65536
4 10000 65536
5 10000 65536
6 10000 65536
7 10000 65536
8 10000 65536
9 10000 65536