101352: [AtCoder]ABC135 C - City Savers
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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