Trong một dây chuyền làm việc của công ty có N công nhân làm N việc. Người ta đánh số cho công nhân từ 1 đến N theo thứ tự đứng trong dây chuyền. Thời gian hoàn thành một công việc của người thứ i là ti phút. Mỗi người cần làm xong công việc của mình nhưng được quyền làm tối đa 2 việc. Vì thế họ có thể phối hợp với người đứng ngay trước mình cùng làm, nếu người thứ i và người thứ i+1 phối hợp thì thời gian làm xong việc cho 2 người là pi. Tìm phương án sao cho N công việc đều hoàn thành với thời gian ít nhất.

Input

• Dòng thứ nhất ghi số N (1 ≤N ≤ 10^6).

• Dòng thứ hai ghi thời gian làm xong việc của từng công nhân tương ứng trong dây chuyền t1, t2,...,tn (1≤ ti ≤60).

• Dòng thứ ba ghi N - 1 số thời gian cùng làm tương ứng cho số cặp công nhân nếu phối hợp p1, p2,..., PN-1(1 ≤p ≤ 100).

Output

Kết quả: ghi ra một số duy nhất ghi tổng thời gian hoàn thành công việc ít nhất của N công nhân.

Ví dụ

Input

5
2 5 7 8 4
3 9 10 10

Output

17