TopCoder

Thumb   5
Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

100.0% (25/25)

Submission's AC Ratio

79.2% (57/72)

Tags

Description

在海上,總共有n艘船,每一艘船上都有一些待運送的貨物。在第i艘船上,待運送的貨物重量是Wi。

在你的手中,則有n-1塊木板。第j塊木板的長度是Lj。每塊木板都可以用來連結兩艘船,被連結的船可以互相到達。

現在,你的工作就是用這n-1塊木板把n艘船連結成一串,並拜訪每一艘船正好一次。每塊木板也只能使用一次。

假設你已經搭載了W的負載重量,那當你拜訪船k之後,負載重量會累加上船k的貨物重量,即負載重量變成W+Wk。

在負載W的狀況下走了長L的路,將會消耗掉W×L單位的體力。請問你完成工作後,最少要消耗多少體力 ?

為了方便起見,木板的重量可以忽略。此外,你可以任選兩艘船做為起點、終點。

Input Format

輸入的第一行是一個正整數n,2 ≤ n ≤ 20,000。

第二行有n個正整數,數字間以空白隔開。第i個正整數Wi代表第i艘船上的貨物重量。1 ≤ Wi ≤ 100,000

第三行則有n-1個正整數,數字間同樣以空白隔開。第j個正整數Lj代表第j塊木板的長度。1 ≤ Lj ≤ 100,000

Output Format

一個正整數C,代表最少要消耗C單位的體力。

Sample Input

5
1 5 3 4 2
6 7 9 8

Sample Output

135

Hints

Problem Source

原TIOJ1610 / Problem Setter: suhorng

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 (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10