Có \(N+1\) thành phố. Thành phố thứ \(i\) đang bị \(A_i\) quái vật tấn công.

Chúng ta có \(N\) anh hùng. Anh hùng thứ \(i\) có thể đánh bại quái vật tấn công thành phố thứ \(i\) hoặc thành phố thứ \((i+1)\), tổng cộng không quá \(B_i\) quái vật.

Hỏi số lượng tối đa quái vật mà các anh hùng có thể hợp tác để đánh bại là bao nhiêu?

Ràng buộc:

• Tất cả giá trị đầu vào là số nguyên.
• \(1 \leq N \leq 10^5\)
• \(1 \leq A_i \leq 10^9\)
• \(1 \leq B_i \leq 10^9\)

ĐỊNH DẠNG ĐẦU VÀO

Đầu vào được cung cấp từ đầu vào chuẩn như sau:

N
A_1 A_2 ... A_{N+1}
B_1 B_2 ... B_N

ĐỊNH DẠNG ĐẦU RA

In ra tổng số quái vật tối đa mà các anh hùng có thể đánh bại.

Ví dụ:

Input

2
3 5 2
4 5

Output

9

Nếu các anh hùng chọn đánh bại quái vật như sau, họ có thể đánh bại tổng cộng chín quái vật, là kết quả tối đa.

Anh hùng đầu tiên đánh bại hai quái vật ở thành phố đầu tiên và hai quái vật ở thành phố thứ hai. Anh hùng thứ hai đánh bại ba quái vật ở thành phố thứ hai và hai quái vật ở thành phố thứ ba.

Input

3
5 6 3 8
5 100 8

Output

22

Giải thích ví dụ mẫu

Với mỗi anh hùng, bạn có thể chọn đánh bại quái vật ở thành phố hiện tại hoặc thành phố tiếp theo, nhưng tổng số quái vật không được vượt quá số lượng tối đa mà anh hùng đó có thể đánh bại. Bạn cần tối ưu hóa việc phân phối quái vật cho các anh hùng để đạt tổng số quái vật tối đa có thể tiêu diệt.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House