Cho dãy số nguyên dương \(A = (a_{1},\ a_{2},\ldots,a_{n})\), phần tử \(a_{i}\) có trọng số \(w_{i}\). Một dãy con \((a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}})\) thỏa mãn:

\[\left\{ \begin{matrix} 1 \leq i_{1} < i_{2} < \ldots < i_{k} \leq n \\ a_{i_{1}} < a_{i_{2}} < \ldots a_{i_{k}} \end{matrix} \right.\ \]

được gọi là một dãy con tăng của dãy \(A\). Chú ý rằng dãy chỉ gồm duy nhất một phần tử của \(A\) cũng được gọi là một dãy con tăng của \(A\).

Yêu cầu: Trong các dãy con tăng của \(A\) hãy tìm ra một dãy có tổng trọng số lớn nhất.

Dữ liệu vào:

+ Dòng 1 chứa số nguyên dương \(n \leq 10^{5}\)

+ Dòng 2 chứa \(n\) số nguyên dương \(a_{1},\ a_{2},\ldots,\ a_{n}\) theo đúng thứ tự đó (\(\forall i:a_{i} \leq 10^{5}\))

+ Dòng 3 chứa \(n\) số nguyên dương \(w_{1},\ w_{2},\ \ldots,\ w_{n}\) theo đúng thứ tự đó (\(\forall i:w_{i} \leq 10^{9})\)

Dữ liệu ra:

+ Ghi 1 số là tổng trọng số lớn nhất của dãy tìm được.

Ví dụ: