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.

Input

• 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)~.

Output

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

Sample Input 1

7
7 10 2 2 7 5 5
8 5 9 7 4 11

Sample Output 1

21