Work
Xem dạng PDF
Trong ~1~ 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 ~1~ 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 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
Vào từ file văn bản WORK.INP:
Dòng thứ nhất ghi số ~N~ (~1 \le N \le 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 truyền ~t_1, t_2, ..., t_N~ (~1 \le t_i \le 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 \le p_i \le 100~)
Output
Ghi ra file WORK.OUT là ~1~ 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.
Sample Input 1
5
2 5 7 8 4
3 9 10 10
Sample Output 1
17
Bình luận
Spoiler