Có N người xếp hàng mua vé dự buổi hoà nhạc, đánh số từ 1 đến N theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, nhưng người bán vé có thể bán cho mỗi người tối đa hai vé. Vì vậy, một số người có thể rời hàng và nhờ người đứng ngay trước mình mua hộ.

Gọi t_i là thời gian để người i mua xong vé cho chính mình. Nếu người i+1 rời hàng và nhờ người i mua hộ thì thời gian để người i mua vé cho cả hai người là r_i. Hãy quyết định ai rời hàng và nhờ người trước mua hộ để tổng thời gian phục vụ nhỏ nhất.

Dữ liệu vào

Dòng 1 chứa số N (1 ≤ N ≤ 60000).

Dòng 2 chứa N số nguyên dương t₁, t₂, …, t_N (1 ≤ t_i ≤ 30000).

Dòng 3 chứa N-1 số nguyên dương r₁, r₂, …, r_N-1 (1 ≤ r_i ≤ 30000).

Kết quả

In ra một số nguyên duy nhất là tổng thời gian phục vụ nhỏ nhất.

Ví dụ 1

Input

5
2 5 7 8 4
4 9 10 10

Output

18

Ví dụ 2

Input

4
5 7 8 4
50 50 50

Output

24