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.

Yêu cầu

Viết chương trình tìm phương án sao cho công việc đều hoàn thành với tổng thời gian ít nhất.

Dữ liệu đầu vào

Gồm ba dòng:

• Dòng đầu tiên ghi số tự nhiên ~n~ ~(1 \le 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 đầu ra

Gồm một số nguyên là tổng thời gian ít nhất để hoàn thành công việc.

Ví dụ

Ví dụ 1

INPUT

5
2 5 7 8 4
4 9 10 10

OUTPUT

18