Sinh nhật của An sắp đến. Bình — bạn thân của An — chuẩn bị đi tìm An để dành cho cậu ấy một bất ngờ.

Thành phố nơi An sống có một tuyến tàu điện ngầm, trên tuyến này có vô số ga. An có thể đợi Bình ở bất kỳ ga nào trên tuyến. Thành phố của An có tất cả $n$ loại vé tàu điện ngầm, loại vé thứ $i$ có giá $a_i$ đồng; người giữ vé đó có thể đi về phía trước hoặc phía sau cố định $b_i$ ga (không được xuống giữa chừng), số lần đi không giới hạn.

Vì kinh phí của Bình có hạn nên cậu chỉ có thể mua nhiều nhất hai loại vé. Hãy giúp Bình tính xem cần tiêu ít nhất bao nhiêu tiền để đảm bảo rằng dù An ở ga tàu điện ngầm nào cũng có thể tìm được cậu ấy; nếu không thể, hãy in ra $-1$ .

Dữ liệu vào

Dòng đầu tiên nhập một số $n$ cho biết có $n$ loại vé tàu điện ngầm được bán.

Dòng thứ hai nhập $n$ số nguyên $a_1,a_2,...,a_n$ , cho biết giá bán của mỗi loại vé là $a_i$ đồng.

Dòng thứ ba nhập $n$ số nguyên $b_1,b_2,...,b_n$ , cho biết mỗi loại vé có thể đi cố định $b_i$ ga.

Dữ liệu ra

In ra đúng một dòng: nếu có thể tìm được An, hãy in ra chi phí ít nhất, ngược lại in ra $-1$ .

Ví dụ

Input

3
5 2 1
3 2 4

Output

6

Ghi chú

Giải thích mẫu Trong ví dụ, có tổng cộng hai cách mua vé để có thể đến được mọi ga tàu điện ngầm:

• Chọn loại vé thứ 1 và loại vé thứ 2, giá 7 đồng.

• Chọn loại vé thứ 1 và loại vé thứ 3, giá 6 đồng.

Vì cần in ra chi phí ít nhất nên đáp án là 6.

Phạm vi dữ liệu

Với 100% dữ liệu chấm:

$1 \le n \le 1000,\ 1 \le a_i \le 10^6,\ 1 \le b_i \le 10^6$