Ở một ngôi đền cổ còn sót lại ~n~ cột được xếp thành ~1~ hàng dọc. Tất cả các cột đều đã bị hư hỏng một phần nên chiều cao của tất cả các cột đều khác nhau. Chiều cao của cột thứ ~i~ là ~h_i~.

Để ngăn không cho các cột tiếp tục bị hư hỏng nữa, ban quản lý đã quyết định lợp mái che cho cột. Mỗi mái che được đặt theo chiều ngang và một đầu được gắn vào đỉnh của một cột nhất định. Có thể lắp đặt mái để che phủ đoạn cột từ ~i~ đến ~j~ ~(1 \le i \le j \le n)~ nếu thỏa một trong các điều kiện sau:

• Nếu cột thứ ~i~ cao hơn tất cả các cột khác trong đoạn ~[i, j]~ thì mái che được cố định đầu bên trái của nó vào cột thứ ~i~, hướng theo chiều từ cột ~i~ đến cột ~j~.

• Nếu cột thứ ~j~ cao hơn tất cả các cột khác trong đoạn ~[i, j]~ thì mái che được cố định đầu bên phải của nó vào cột thứ ~j~, hướng theo chiều từ cột ~j~ đến cột ~i~.

Ở đầu mỗi cột, không thể gắn nhiều hơn một mái che. Chi phí gắn mái che vào cột thứ ~i~ là ~c_i~, bất kể nó hướng về bên trái hay bên phải và có bao nhiêu cột. Hãy gắn mái che vào các cột sao cho mỗi cột được ít nhất một mái che và tổng chi phí là nhỏ nhất.

Input

Dòng đầu tiên chứa số nguyên ~n~ là số cột ~(1 \le n \le 200000)~.

Dòng thứ hai chứa các giá trị ~h_i~ là chiều cao của cột ~i~ ~(1 \le h_i \le 10^9)~.

Dòng thứ ba chứa các giá trị ~c_i~ là chi phí gắn mái che vào cột ~i~ ~(1 \le c_i \le 10^9)~.

Output

In ra chi phí tối thiểu để lợp mái che cho tất cả các cột.

Sample Input 1

3
3 10 7
2 5 2

Sample Output 1

7