造橋人的使命就是造橋。
現在有 N 塊板子，每塊板子長度 Li
每回合，造橋人會選擇一塊還沒被使用的板子用來造橋。
為了感謝造橋人的辛勞，各區的民眾準備了 N 份禮物要給他。
每當造橋人搭建一塊板子，大家就會給他一份重量 Wi 的謝禮。
造橋人會把所得到的禮物扛在身上，並往前繼續造橋。
其中，當扛著總重 W 的謝禮，走過 L 長的距離時，將對應付出 W x L 單位的體力。
因為每一區民眾的禮物都已經準備好，所以 N 份禮物的獲得順序不能變動；
但是造橋人可以改變所使用的木板順序。
舉例來說，假設 N = 3，
N 塊板子分別為：板子0(長度2), 板子1(長度6), 板子2(長度8)N 個禮物分別為：禮物0(重量7), 禮物1(重量5), 禮物2(重量3)
假設造橋順序為：板子0 → 板子1 → 板子2
則耗費的體力將為：
搭建板子0，並且手上沒有任何禮物：0 x L0 = 0 x 2 = 0
搭建板子1，並且手上擁有禮物0 ：7 x L1 = 7 x 6 = 42
搭建板子2，並且手上擁有禮物0,1 ：12 x L2 = 12 x 8 = 96
完成搭建，並且手上擁有禮物0,1,2：15 x 不走動 = 15 x 0 = 0
也就是總共付出 0 + 42 + 96 + 0 = 138 單位的體力
但若改為造橋順序：板子2 → 板子1 → 板子0
則耗費的體力將為：
搭建板子2，並且手上沒有任何禮物：0 x L2 = 0 x 8 = 0
搭建板子1，並且手上擁有禮物0 ：7 x L1 = 7 x 6 = 42
搭建板子0，並且手上擁有禮物0,1 ：12 x L0 = 12 x 2 = 24
完成搭建，並且手上擁有禮物0,1,2：15 x 不走動 = 15 x 0 = 0
也就是總共付出 0 + 42 + 24 + 0 = 66 單位的體力
可以看出 板子2 → 板子1 → 板子0 會是比較好的木板使用順序。
在禮物獲得順序不能被變動的情況，
請協助計算最佳木板使用順序策略下，造橋人所必須付出的最小體力值。
謝謝你
造橋人，我的超人
第一行有一個正整數 N，代表木板和禮物總數
1 ≤ N ≤ 105
第二行由左至右有 N 個正整數 Li，代表可使用的木板長度
1 ≤ Li ≤ 1000
第三行由左至右有 N 個正整數 Wi，代表依序獲得的禮物重量
1 ≤ Wi ≤ 1000
最小所需付出體力值
3 2 6 8 7 5 3
66
3 2 2 2 7 5 3
38
10%：所有 Li 皆相同
10%：Li 只有兩種
30%：N ≤ 100
50%：無特別限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 32189 | mushroom.cs9 ... (mushroom) | i792 | 393 | 2022-09-20 09:55 |