Nhờ mua hộ vé

Tại quầy bán vé của một buổi hòa nhạc có \(N\) người xếp hàng, đánh số từ \(1\) đến \(N\) từ đầu hàng đến cuối hàng. Mỗi người cần đúng một vé. Nhân viên bán vé cho phép mỗi người mua tối đa hai vé, nên một số người có thể rời hàng và nhờ người đứng ngay trước mình mua hộ.

Nếu người \(i\) tự mua vé cho riêng mình thì mất \(t_i\) giây. Nếu người \(i\) mua hộ cả người \(i+1\) (người \(i+1\) rời hàng) thì tổng thời gian phục vụ cho hai người là \(r_i\) giây. Mỗi người chỉ được mua hộ tối đa một người, và người đã nhờ mua hộ thì không mua hộ ai khác.

Hãy tính tổng thời gian phục vụ nhỏ nhất.

Input

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(t_1, \dots, t_N\).
• Dòng thứ ba chứa \(N-1\) số nguyên \(r_1, \dots, r_{N-1}\) (nếu \(N = 1\) dòng này để trống hoặc không có).

Output

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

Constraints

• \(1 \le N \le 60000\)
• \(1 \le t_i \le 30000\), \(1 \le r_i \le 30000\)

Sample Input 1

6
3 6 4 7 2 5
5 9 6 8 4

Sample Output 1

15

Sample Input 2

4
6 2 9 3
20 4 5

Sample Output 2

13

Explanation

Ví dụ 1: ghép các cặp \((1,2), (3,4), (5,6)\) mất \(5 + 6 + 4 = 15\) giây. Ví dụ 2: người 1 tự mua (\(6\)), người 2 mua hộ người 3 (\(4\)), người 4 tự mua (\(3\)), tổng \(13\).