文無第一武無第二 (AP325 P-6-22)

在一個群體中有 \(n\) 個成員，編號為 \(1 \sim n\)，第 \(i\) 個人的戰力為 \(p[i]\)，現在想要挑選一些人組成一個團隊擔任特別的任務。目前除了戰力外，還考量兩項能力值：程式力 \(c[i]\) 與數學力 \(m[i]\)。俗話說「文無第一，武無第二」，如果挑選的人員中某一位的程式力與數學力都不如另外一位的話，他就會非常的沮喪而導致團隊總戰力受到傷害。你的目標是要挑出一個戰力總和最大的團隊，而且如果 \(i\) 與 \(j\) 都是被挑選的人的話，不允許 \(c[i] < c[j]\) 且 \(m[i] < m[j]\)。

輸入格式

第一行是正整數 \(n\)。第二行有 \(n\) 個正整數，代表戰力 \(p[1] \sim p[n]\)；第三行有 \(n\) 個非負整數，代表程式力 \(c[1] \sim c[n]\)；第四行有 \(n\) 個非負整數，代表數學力 \(m[1] \sim m[n]\)。同行數字間以空白隔開。

限制

• \(1 \le n \le 10^5\)。
• 戰力 \(p[i]\) 為正整數，且戰力總和不超過 \(10^9\)。
• 每個程式力與數學力均為不超過 \(10^8\) 的非負整數。

輸出格式

輸出最大戰力總和。

評分說明

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

範例輸入 1

5
2 4 1 3 7
1 2 3 3 4
6 7 4 5 1

範例輸出 1

15

範例輸入 2

5
1 2 3 4 9
4 5 4 5 8
3 6 4 5 7

範例輸出 2

9

範例說明

範例一：挑選 \(i = 2 \sim 5\)，戰力總和 \(4 + 1 + 3 + 7 = 15\)。

範例二：挑選 \(i = 5\)，戰力總和 \(9\)。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 6 章 P-6-22，第 210 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。