TopCoder

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

User's AC Ratio

98.2% (55/56)

Submission's AC Ratio

73.3% (140/191)

Tags

Description

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

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

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

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

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

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

Input Format

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

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

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

Output Format

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

Sample Input 1

5
1 5 3 4 2
6 7 9 8

Sample Output 1

135

Hints

Problem Source

原TIOJ1610 / Problem Setter: suhorng
$\LaTeX$ Fixed by Seanliu on 20210316

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 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