Dây chuyền sản xuất

Trong một dây chuyền sản xuất tự động có $n$ cánh tay ROBOT được đánh số từ $1$ đến $n$, các cánh tay ROBOT này phải hoàn thành $n$ công việc theo thứ tự đã được đánh số. Thời gian hoàn thành độc lập công việc của cánh tay thứ $i$ là $t_i$ giây. Nếu cánh tay thứ $i$ và thứ $i+1$ phối hợp thì thời gian làm xong việc cho cả hai là $p_i$ giây. Viết chương trình tìm phương án sao cho $n$ công việc đều hoàn thành với tổng thời gian ít nhất.

Các công việc được thực hiện lần lượt, nên tổng thời gian là tổng thời gian của các phần việc: mỗi cánh tay hoặc làm độc lập công việc của mình, hoặc phối hợp với đúng một cánh tay kề bên (thứ $i$ với thứ $i+1$) để cùng làm xong hai công việc $i$ và $i+1$. Mỗi cánh tay chỉ thuộc nhiều nhất một cặp phối hợp.

Dữ liệu vào

• Dòng đầu tiên ghi số tự nhiên $n$ ($1<n\le {10}^6$);
• Dòng thứ hai ghi $n$ số $t_i$ ($1\le t_i\le 60$, $1\le i\le n$);
• Dòng thứ ba ghi $n-1$ số $p_i$ ($1\le p_i\le 100$).

Dữ liệu ra

Dòng đầu tiên ghi tổng thời gian ít nhất để hoàn thành công việc.

Ràng buộc

• $1<n\le {10}^6$.
• $1\le t_i\le 60$.
• $1\le p_i\le 100$.

Ví dụ