10733: ABC135 - C - City Savers
[Creator : ]
Description
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?
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?
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$
```
```
$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.
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$
- $1 \leq N \leq 10^5$
- $1 \leq A_i \leq 10^9$
- $1 \leq B_i \leq 10^9$
Sample 1 Input
2
3 5 2
4 5
Sample 1 Output
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 2 Input
3
5 6 3 8
5 100 8
Sample 2 Output
22
Sample 3 Input
2
100 1 1
1 100
Sample 3 Output
3