TopCoder

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

User's AC Ratio

100.0% (19/19)

Submission's AC Ratio

82.8% (48/58)

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

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