TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

90.6% (29/32)

Submission's AC Ratio

31.7% (64/202)

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 1

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

Sample Output 1

11200

Hints

Problem Source

原TIOJ1785 / problem setter: jeremy89183

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10