uou và Prototype phát hiện ra kho chứa mẫu vật. Có \(n\) kiện hàng, kiện thứ \(i\) có khối lượng \(w_i\) và giá trị \(v_i\). Con tàu có một robot vận chuyển nhưng nó có một lỗi logic: Nếu nó lấy kiện hàng \(i\) và \(j\) (\(i < j\)), thì tất cả các kiện hàng \(k\) nằm giữa (\(i < k < j\)) mà có \(w_k < \min(w_i, w_j)\) sẽ bị hỏng và không thể lấy được nữa.

Yêu cầu: Tính tổng giá trị lớn nhất Prototype và uou có thể thu thập được.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 5 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(w_1, w_2, \dots, w_n\) (\(1 \le w_i \le 10^9\)).
• Dòng thứ ba chứa \(n\) số nguyên \(v_1, v_2, \dots, v_n\) (\(1 \le v_i \le 10^9\)).

Output

• Một số nguyên duy nhất là tổng giá trị \(v_i\) lớn nhất thu thập được.

Example

6
10 5 15 2 20 8
100 50 200 30 150 70

420

Scoring

• Subtask 1 (20% số điểm): \(n \le 20\).
• Subtask 2 (30% số điểm): \(n \le 2000\).
• Subtask 3 (50% số điểm): \(n \le 5 \cdot 10^5\).