物品堆疊 (APCS 2017-10 高級)

某個自動化系統中有一個存取物品的子系統，該系統是將 \(N\) 個物品堆在一個垂直的貨架上，每個物品各佔一層。系統運作的方式如下：每次只會取用一個物品，取用時必須先將在其上方的物品貨架升高，取用後必須將該物品放回，然後將剛才升起的貨架降回原始位置，之後才會進行下一個物品的取用。

每一次升高某些物品所需要消耗的能量是以這些物品的總重來計算，在此我們忽略貨架的重量以及其他可能的消耗。現在有 \(N\) 個物品，第 \(i\) 個物品的重量是 \(w(i)\) 需要取用的次數為 \(f(i)\)，我們需要決定如何擺放這些物品的順序來讓消耗的能量越小越好。

舉例來說，有兩個物品 \(w(1)=1\)、\(w(2)=2\)、\(f(1)=3\)、\(f(2)=4\)，也就是說物品 \(1\) 的重量是 \(1\) 需取用 \(3\) 次，物品 \(2\) 的重量是 \(2\) 需取用 \(4\) 次。我們有兩個可能的擺放順序（由上而下）：

• \((1,2)\)，也就是物品 \(1\) 放在上方，\(2\) 在下方。那麼，取用 \(1\) 的時候不需要能量，而每次取用 \(2\) 的能量消耗是 \(w(1)=1\)，因為 \(2\) 需取用 \(f(2)=4\) 次，所以消耗能量數為 \(w(1)*f(2)=4\)。
• \((2,1)\)，也就是物品 \(2\) 放在 \(1\) 的上方。那麼，取用 \(2\) 的時候不需要能量，而每次取用 \(1\) 的能量消耗是 \(w(2)=2\)，因為 \(1\) 需取用 \(f(1)=3\) 次，所以消耗能量數 = \(w(2)*f(1)=6\)。

在所有可能的兩種擺放順序中，最少的能量是 \(4\)，所以答案是 \(4\)。再舉一例，若有三物品而 \(w(1)=3\)、\(w(2)=4\)、\(w(3)=5\)、\(f(1)=1\)、\(f(2)=2\)、\(f(3)=3\)。假設由上而下以 \((3,2,1)\) 的順序，此時能量計算方式如下：取用物品 \(3\) 不需要能量，取用物品 \(2\) 消耗 \(w(3)*f(2)=10\)，取用物品 \(1\) 消耗 \((w(3)+w(2))*f(1)=9\)，總計能量為 \(19\)。如果以 \((1,2,3)\) 的順序，則消耗能量為 \(3*2+(3+4)*3=27\)。事實上，我們一共有 \(3!=6\) 種可能的擺放順序，其中順序 \((3,2,1)\) 可以得到最小消耗能量 \(19\)。

輸入格式

輸入的第一行是物品件數 \(N\)，第二行有 \(N\) 個正整數，依序是各物品的重量 \(w(1)\)、\(w(2)\)、…、\(w(N)\)，重量皆不超過 \(1000\) 且以一個空白間隔。第三行有 \(N\) 個正整數，依序是各物品的取用次數 \(f(1)\)、\(f(2)\)、…、\(f(N)\)，次數皆為 \(1000\) 以內的正整數，以一個空白間隔。

輸出格式

輸出最小能量消耗值，以換行結尾。所求答案不會超過 \(63\) 個位元所能表示的正整數。

範例輸入 1

2
20 10
1 1

範例輸出 1

10

範例輸入 2

3
3 4 5
1 2 3

範例輸出 2

19

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制 (time limit) 均為 \(1\) 秒，依正確通過測資筆數給分。其中：

第 1 子題組 10 分，\(N = 2\)，且取用次數 \(f(1)=f(2)=1\)。

第 2 子題組 20 分，\(N = 3\)。

第 3 子題組 45 分，\(N \le 1,000\)，且每一個物品 \(i\) 的取用次數 \(f(i)=1\)。

第 4 子題組 25 分，\(N \le 100,000\)。

題目來源

2017 年 10 月 28 日 APCS 實作題第 4 題，官方題本：https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2018/12/1061028APCSImplementation.pdf