/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N+1 個の街があり、i 番目の街は A_i 体のモンスターに襲われています。
N 人の勇者が居て、i 番目の勇者は i 番目または i+1 番目の街を襲っているモンスターを合計で B_i 体まで倒すことができます。
N 人の勇者がうまく協力することで、合計して最大で何体のモンスターを倒せるでしょうか。
制約
- 入力は全て整数である。
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 ... A_{N+1}
B_1 B_2 ... B_N
出力
合計して倒せるモンスターの数の最大値を出力せよ。
入力例 1
2 3 5 2 4 5
出力例 1
9
以下のようにモンスターを倒すと、合計 9 体のモンスターを倒すことができ、このときが最大です。
- 1 番目の勇者が 1 番目の街を襲っているモンスターを 2 体、2 番目の街を襲っているモンスターを 2 体倒します。
- 2 番目の勇者が 2 番目の街を襲っているモンスターを 3 体、3 番目の街を襲っているモンスターを 2 体倒します。
入力例 2
3 5 6 3 8 5 100 8
出力例 2
22
入力例 3
2 100 1 1 1 100
出力例 3
3
Score : 300 points
Problem Statement
There are N+1 towns. The i-th town is being attacked by A_i monsters.
We have N heroes. The i-th hero can defeat monsters attacking the i-th or (i+1)-th town, for a total of at most B_i monsters.
What is the maximum total number of monsters the heroes can cooperate to defeat?
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_{N+1}
B_1 B_2 ... B_N
Output
Print the maximum total number of monsters the heroes can defeat.
Sample Input 1
2 3 5 2 4 5
Sample Output 1
9
If the heroes choose the monsters to defeat as follows, they can defeat nine monsters in total, which is the maximum result.
- The first hero defeats two monsters attacking the first town and two monsters attacking the second town.
- The second hero defeats three monsters attacking the second town and two monsters attacking the third town.
Sample Input 2
3 5 6 3 8 5 100 8
Sample Output 2
22
Sample Input 3
2 100 1 1 1 100
Sample Output 3
3