Có ~N~ bông hoa được xếp thành một hàng trong vườn hoa của Taro. Với mỗi ~i\,(1 \le i \le N)~, chiều cao và vẻ đẹp của bông hoa thứ ~i~ từ trái sang phải lần lượt là ~h_i~ và ~a_i~. Trong vườn hoa, chiều cao của các bông hoa ~h_1, h_2, \ldots, h_N~ phân biệt đôi một với nhau.
Taro đang nhổ một số bông hoa đi để những bông hoa còn lại trong vườn thỏa mãn điều kiện sau đây:
- Chiều cao của các bông hoa còn lại tăng dần từ trái sang phải.
Taro muốn vườn hoa của mình là đẹp nhất có thể (dĩ nhiên, ai mà chẳng muốn như vậy), vậy nên Taro muốn bỏ đi các bông hoa sao cho tổng vẻ đẹp của những bông hoa còn lại là lớn nhất. Tuy nhiên, Taro đang bận làm bài tập nên đã nhờ bạn làm giúp việc này. Hãy giúp Taro và in ra tổng vẻ đẹp lớn nhất có thể của các bông hoa còn lại.
Input
Dòng thứ nhất chứa một số nguyên ~N\,(1 \le N \le 2 \times 10^5)~.
Dòng thứ hai chứa ~N~ số nguyên ~h_i\,(1 \le h_i \le N)~ phân biệt đôi một.
Dòng thứ ba chứa ~N~ số nguyên ~a_i\,(1 \le a_i \le 10^9)~.
Output
In ra tổng vẻ đẹp lớn nhất có thể của những bông hoa còn lại.
Sample 1
Input
4
3 1 4 2
10 20 30 40
Output
60
Giải thích
Tổng vẻ đẹp lớn nhất của vườn hoa có thể là ~60~, bằng cách giữ lại các bông hoa thứ hai và thứ tư từ trái qua phải.
Sample 2
Input
1
1
10
Output
10
Giải thích
Vườn hoa đã thỏa mãn điều kiện đề bài từ ban đầu.
Sample 3
Input
5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000
Output
5000000000
Sample 4
Input
9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5
Output
31
Giải thích
Tổng vẻ đẹp lớn nhất của vườn hoa có thể là ~31~, bằng cách giữ lại các bông hoa thứ hai, thứ ba, thứ sáu, thứ tám và thứ chín từ trái qua phải.
Lưu ý
Đáp án có thể vượt quá giới hạn của kiểu biến số nguyên 32-bit.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
hay quá
This comment is hidden due to too much negative feedback. Show it anyway.
Bài rất hay và bổ ích.