隔離採礦 (AP325 Q-6-24)

外星採礦隊在烏邦圖星球已經探勘到某種礦物的礦脈，這條礦脈是一個筆直的直線，且一共有 \(n\) 個可以挖礦井的地點，這些地點就稱為可開採點。所有的可開採點由 \(1\) 到 \(n\) 依序編號，第 \(i\) 個可開採點的高度為 \(h(i)\) 而開採價值為 \(v(i)\)。

現在希望能找出某些可開採點來實際進行鑽井挖礦，因為安全因素，任兩個礦井之間必須有另外一個開採點，其高度超過這兩個礦井。身為外星採礦隊的程式設計師，你的目標是計算出最大的開採價值總和。

下圖是一個 \(n = 10\) 的例子，圖中各點的高度為 \(y\) 軸座標，而開採價值則標註於各點旁邊。如圖所示，各點的高度依序是 \(h = (2, 5, 3, 2, 4, 2, 3, 1, 4, 3)\)，而開採價值則依序是 \(v = (1, 8, 3, 1, 5, 1, 4, 2, 4, 2)\)，也就是說 \(h(1) = 2, h(2) = 5, \ldots, h(10) = 3\)，而 \(v(1) = 1, v(2) = 8, \ldots, v(10) = 2\)。在此例中，最佳的開採方式是圖中被圓圈所圈起來的四個點，所能獲得的最大開採價值總和為 \(1 + 3 + 4 + 2 = 10\)。你可以看到，任兩個實際開採點之間都有一個高度更高的點。

輸入格式

第一行是一個正整數 \(n\)，代表可開採點的數量。第二行是 \(n\) 個非負整數，依序代表每一點的高度 \(h(1), h(2), \ldots, h(n)\)；第三行是 \(n\) 個正整數，依序代表每一點的開採價值 \(v(1), v(2), \ldots, v(n)\)。每一行相鄰數字間以一空白間隔。

限制

• \(1 \le n \le 10^6\)。
• 每一點的高度不會超過 \(10^9\)，價值不會超過 \(10^5\)。
• 每筆測資的答案不超過 \(2 \times 10^9\)。

輸出格式

輸出為一整數，代表最大的開採價值總和。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

10
2 5 3 2 4 2 3 1 4 3
1 8 3 1 5 1 4 2 4 2

範例輸出 1

10

範例輸入 2

5
3 3 3 3 3
5 3 2 3 4

範例輸出 2

5

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 6 章 Q-6-24，第 215 頁；經作者同意於 AACPOJ 免費公開。原題出自 108 學年度全國高級中等學校資訊學科能力競賽。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。