Mua vé

Có \(n\) người xếp hàng mua vé dự hòa nhạc, họ lần lượt xếp số thứ tự từ \(1\) đến \(n\) (với người 1 là người đầu hàng). Mỗi người cần chính xác một vé, tuy nhiên mỗi người có thể mua hai vé. Vì vậy, người thứ \(i\) có thể nhờ người đứng trước là người thứ \(i-1\) mua hộ vé.

Thời gian để người thứ \(i\) mua vé cho mình là \(t_i\). Nếu người \(i\) nhờ người \(i-1\) mua vé, thì thời gian để người \(i-1\) mua cả hai vé là \(r_i\).

Hãy tìm thời gian nhỏ nhất để có thể bán vé cho toàn bộ \(n\) người.

Input

Dòng đầu tiên gồm số nguyên \(n\) (\(1 \le n \le 10^5\)) --- số lượng người.

Dòng thứ hai gồm \(n\) số nguyên \(t_1, t_2, ..., t_n\) (\(1 \le t_i \le 10^4\)) --- thời gian để mỗi người tự mua vé.

Dòng thứ ba gồm \(n - 1\) số nguyên \(r_2, r_3, ..., r_n\) (\(1 \le r_i \le 10^4\)) --- thời gian để người \(i-1\) mua hai vé.

Output

In ra một số nguyên --- thời gian nhỏ nhất để tất cả \(n\) người đều có vé.

Example

Input:

5
2 5 7 8 4
4 9 10 10

Output:

18

Notes

• Người thứ 2 mua vé cho cả người 1 và 2, mất 4 đơn vị thời gian.

• Người thứ 4 mua vé cho người 3 và 4, mất 10 đơn vị thời gian.

• Người thứ 5 tự mua vé, mất 4 đơn vị thời gian.

Tổng thời gian là \(4 + 10 + 4 = 18\).