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à ~t_i~ 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à ~p_i~. 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 ~t_1, t_2,...,t_n~ (1 ≤ ~t_i~ ≤ 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 ~p_1, p_2,..., P_{N-1}~ (1 ≤ ~p_i~ ≤ 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