Dãy tăng giá trị (Maximum-Value Increasing Subsequence)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ sản phẩm được đưa lên dây chuyền theo thứ tự từ $1$ đến $N$.

Sản phẩm thứ $i$ có độ cao $H_i$ và giá trị $V_i$.

Ta được chọn một dãy con không rỗng của các sản phẩm và phải giữ nguyên thứ tự tương đối ban đầu.

Giả sử các chỉ số được chọn là

Dãy sản phẩm được chọn được gọi là hợp lệ nếu độ cao của chúng tăng nghiêm ngặt:

Giá trị của một dãy được chọn bằng tổng giá trị của tất cả sản phẩm trong dãy đó.

Hãy tìm tổng giá trị lớn nhất của một dãy sản phẩm hợp lệ.

Input

• Dòng đầu chứa số nguyên $N$ — số lượng sản phẩm.
• Dòng thứ hai chứa $N$ số nguyên $H_1,H_2,\ldots,H_N$ — độ cao của các sản phẩm.
• Dòng thứ ba chứa $N$ số nguyên $V_1,V_2,\ldots,V_N$ — giá trị tương ứng của các sản phẩm.

Output

In ra một số nguyên duy nhất — tổng giá trị lớn nhất có thể đạt được của một dãy sản phẩm hợp lệ.

Subtask

• Subtask 1: $1 \le N \le 20$; $1 \le H_i,V_i \le 10^9$. Time Limit: 1,0 giây.
• Subtask 2: $1 \le N \le 2000$; $1 \le H_i,V_i \le 10^9$. Time Limit: 1,0 giây.
• Subtask 3: $1 \le N \le 2\cdot10^5$; $1 \le H_i \le 2\cdot10^5$; $1 \le V_i \le 10^9$. Time Limit: 1,5 giây.
• Subtask 4: $1 \le N \le 2\cdot10^5$; $1 \le H_i,V_i \le 10^9$. Time Limit: 2,0 giây.

Ví dụ

Ví dụ 1

Input

5
3 1 4 2 5
5 6 4 7 3

Output

16

Giải thích

Có thể chọn các sản phẩm ở vị trí $2$, $4$ và $5$.

Độ cao của chúng lần lượt là

nên tạo thành một dãy hợp lệ.

Tổng giá trị nhận được là

Không có dãy hợp lệ nào có tổng giá trị lớn hơn, vì vậy đáp án là $16$.

Ví dụ 2

Input

4
4 3 2 1
1 2 3 4

Output

4

Giải thích

Dãy độ cao

giảm nghiêm ngặt, vì vậy không thể chọn đồng thời hai sản phẩm mà vẫn thỏa mãn điều kiện độ cao tăng nghiêm ngặt.

Do đó chỉ có thể chọn một sản phẩm. Sản phẩm thứ $4$ có giá trị lớn nhất bằng $4$, nên đáp án là $4$.