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.

Input

• Dòng đầu tiên ghi số tự nhiên n (~1 ≤ n ≤ 10^6~).

• Dòng thứ hai ghi n số ~t~ (~1 ≤ t_i ≤ 60, 1 ≤ i ≤ n~).

• Dòng thứ ba ghi ~n - 1~ số ~p_i~ (~1 ≤ p_i ≤ 100~).

Output

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

Example

Input

5
2 5 7 8 4
4 9 10 10

Output

18