Kanino và bài toán bông hoa(*)

Xem PDF



Tác giả:
Dạng bài
Điểm: 1600 (p) Thời gian: 2.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

\(N\) bông hoa được sắp thành \(1\) hàng. Với mỗi \(i(1\le i\le N)\), chiều cao và độ "đẹp" của bông hoa thứ \(i\) lần lượt là \(h_i\)\(a_i\). Ở đây \(h_1,h_2,...,h_N\) phân biệt với nhau từng đôi một!

\(Kaninho\) muốn lấy đi vài bông hoa để những bông hoa còn lại thỏa mãn điều kiện sau :

  • Chiều cao của những bông hoa còn lại là một dãy đơn điều tăng dần từ trái sang phải

Yêu cầu: Tìm độ "đẹp" lớn nhất có thể có của những bông hoa còn lại

Input

  • Dòng thứ nhất chứa số nguyên \(N(1\le N\le 2\times 10^5)\)

  • Dòng thứ hai chứa \(n\) số nguyên \(h_1,h_2,...,h_N(1\le h_i\le N)\)

  • Dòng thứ ba chứa \(n\) số nguyên \(a_1,a_2,...,a_N(1\le a_i\le 10^9)\)

Output

  • In ra đáp án cần tìm

Example

Test 1

Input
4
3 1 4 2
10 20 30 40
Output
60
Note

Giải thích: Ở đây ta sẽ lấy đi bông hoa thứ \(1\) và bông hoa thứ \(3\). Khi đó những bông hoa còn lại thỏa mãn yêu cầu bài toán và chúng có tổng độ "đẹp" lớn nhất là \(60\)


Bình luận


  • 0
    jumptozero 10:39 a.m. 31 Tháng 7, 2020

    À các anh cứ comment các bài khác nữa nhé !!!


    • 0
      tuanlinh 10:34 a.m. 31 Tháng 7, 2020

      trong đề n<=2e5 mà các test n tối đa chỉ có 15 ?

      1 phản hồi