Chụp ảnh

Alice đang thăm thành phố New York. Để chuyến đi trở nên vui vẻ, Alice sẽ chụp ảnh đường chân trời của thành phố và tặng bộ ảnh làm quà cho Bob. Tuy nhiên, cô ấy muốn tìm bộ ảnh với vẻ đẹp tối đa và cô ấy cần sự giúp đỡ của bạn.

Có $N$ tòa nhà trong thành phố, tòa nhà thứ $i$ có chiều cao $h_i$ ($h_i>0$). Tất cả $N$ độ cao của tòa nhà trong thành phố là khác nhau. Ngoài ra, mỗi tòa nhà đều có một giá trị vẻ đẹp $b_i$. Lưu ý rằng vẻ đẹp có thể dương hoặc âm, vì cũng có những tòa nhà xấu xí trong thành phố.

Bộ ảnh bao gồm một hoặc nhiều ảnh chụp các tòa nhà ở đường chân trời. Mỗi ảnh bao gồm một hoặc nhiều tòa nhà trong đường chân trời tạo thành một phân đoạn chỉ số liền kề. Mỗi tòa nhà cần thuộc chính xác một ảnh. Điều này có nghĩa là nếu một tòa nhà không xuất hiện trong bất kỳ ảnh nào hoặc nếu một tòa nhà xuất hiện trong nhiều ảnh, thì bộ ảnh đó không hợp lệ.

Vẻ đẹp của một bức ảnh tương đương với vẻ đẹp của tòa nhà thấp nhất trong đó. Vẻ đẹp tổng thể của một bộ ảnh là tổng vẻ đẹp của tất cả những bức ảnh trong đó.

Yêu cầu: Bạn hãy giúp Alice tìm ra vẻ đẹp tối đa mà một bộ ảnh hợp lệ có thể có.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$ ($1\le N\le 3·{10}^5$), số tòa nhà trên đường chân trời.
• Dòng thứ hai chứa $N$ số nguyên phân biệt $h_1,h_2,\dots ,h_N$ ($1\le h_i\le N$). Số thứ $i$ thể hiện chiều cao của tòa nhà thứ $i$.
• Dòng thứ ba chứa $N$ số nguyên $b_1,b_2,\dots ,b_N$ ($-{10}^9\le b_i\le {10}^9$). Số thứ $i$ đại diện cho vẻ đẹp của tòa nhà $i$.

Dữ liệu ra

Gồm một số nguyên là vẻ đẹp tối đa mà Alice có thể đạt được để có một bộ ảnh hợp lệ về đường chân trời.

Ràng buộc

• $1\le N\le 3·{10}^5$.
• $1\le h_i\le N$, các $h_i$ đôi một khác nhau.
• $-{10}^9\le b_i\le {10}^9$.
• Có $50\%$ số test có $N\le {10}^3$.
• $50\%$ số test còn lại có ${10}^3<N\le 3·{10}^5$.

Ví dụ