Bài tập chưa có test

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.

Dữ liệu vào

• Dòng thứ nhất ghi số ~N~
• 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~ .
• 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}~

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.

Giới hạn:

• ~1<N≤10^6~
• ~1≤t_i≤60~
• ~1≤ p_i ≤ 100~

Ví dụ:

Input

5
2  5  7  8   4
3  9  10  10 

Output

17