Hôm nay anh em nhà Hiếu chơi một trò chơi với hoán vị. Anh em nhà Hiếu được cho một dãy hoán vị \(p_{1}, p_{2}, \ldots, p_{n}\) (hoán vị là một dãy số mà mỗi số nguyên từ \(1\) tới \(n\) được xuất hiện chính xác một lần). Trọng số của phần tử thứ \(i\) trong hoán vị là \(a_{i}\).

Đầu tiên, Hiếu và em trai chọn một phần tử thứ \(i\) \((1 \leq i < n)\), sau đó chia dãy hoán vị làm hai phần. Hiếu sẽ lấy các phần tử của dãy hoán vị từ vị trí thứ \(1\) đến vị trí thứ \(i\) (lấy các phần tử có giá trị từ \(p_{1}\) đến \(p_{i}\)), còn em trai của Hiếu sẽ lấy các phần tử của dãy hoán vị từ vị trí thứ \(i + 1\) đến vị trí thứ \(n\) (lấy các phần tử có giá trị từ \(p_{i + 1}\) đến \(p_{n}\)).

Sau đó, Hiếu và em trai thực hiện "trao đổi" các phần tử cho nhau. Cụ thể hơn, Hiếu có thể đưa cho em trai một, hoặc vài số (có thể là không đưa) bất kì trong dãy hoán vị của Hiếu cho em trai. Ngược lại, em trai cũng có thể đưa Hiếu một, hoặc vài số (cũng có thể không đưa) bất kì trong dãy hoán vị của mình cho Hiếu. Việc trao đổi số \(p_{i}\) sẽ tốn một chi phí là \(a_{i}\).

Mục tiêu của trò chơi là trao đổi các số trong dãy hoán vị, sao cho giá trị của số lớn nhất trong các phần tử mà Hiếu sở hữu sau khi trao đổi nhỏ hơn giá trị của số nhỏ nhất trong các phần tử mà em trai của Hiếu sở hữu sau khi trao đổi. Trò chơi cũng được tính là thành công nếu một trong hai dãy trở thành dãy rỗng.

Ví dụ, nếu \(p = [3, 1, 2]\) và \(a = [7, 1, 5]\) thì họ có thể thực hiện trò chơi như sau: chia dãy \(p\) thành hai phần là \([3, 1]\) và \([2]\) rồi đổi chỗ phần tử có giá trị bằng \(2\) từ phần thứ hai sang phần thứ nhất (chi phí là \(5\)). Nếu \(p = [3, 5, 1, 6, 2, 4], a = [9, 2, 9, 9, 3, 9]\) thì ta chia \(p\) thành hai phần là \([3, 5, 1]\) và \([6, 2, 4]\), và đổi phần tử có giá trị bằng \(5\) từ phần thứ nhất sang phần thứ hai, đổi phần tử có giá trị bằng \(2\) từ phần thứ hai sang phần thứ nhất (chi phí là \(5\)).

Bạn hãy giúp anh em nhà Hiếu tính chi phí nhỏ nhất cần sử dụng để sau khi thực hiện tất cả các thao tác, hai dãy mà anh em nhà Hiếu nhận được là thỏa mãn yêu cầu đề bài.

Input

• Dòng thứ nhất chứa một số nguyên dương \(n\) \((2 \leq n \leq 2 \times 10^{5})\) là độ dài của hoán vị.
• Dòng thứ hai chứa \(n\) số nguyên \(p_{1}, p_{2}, \ldots, p_{n}\) \((1 \leq p_{i} \leq n)\). Dữ liệu đảm bảo dãy chứa các phần tử có giá trị từ \(1\) đến \(n\), mỗi giá trị xuất hiện chính xác một lần.
• Dòng thứ ba chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\).

Output

• Đưa ra một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 5000\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3
3 1 2
7 2 5

5