Shooting Balloons

Time Limit: 1000ms

Memory Limit: 256MB

Shooting Balloons

Submissions Submit

Because any contest must have lots of balloons, Zaid decided to use them, so he created a game that contains $n$ levels, where the $i_{th}$ level contains $a_i$ balloon.
Your goal is to shoot all balloons in all levels, to do that you are given a gun that can hold infinite number of bullets but initially it has no bullets inside its magazine. Once you enter the $i_{th}$ level for the first time the number of bullets in the magazine will instantly be increased by $b_i$.
Since you don't have lots of time, you need to finish the game in minimum time possible. What you can do In one second is one of these operations,  
if you are currently at level $i$ where $(1 \leq i < n)$, you can go to level $i + 1$.
if you are currently at level $i$ where $(1 < i \leq n)$, you can go to level $i - 1$.
if there is at least one balloon left in the current level and you have at least one bullet left in your gun, you can shoot that balloon, after that the number of bullets in your magazine and the number of balloons in the current level will be decreased by one.
You start the game at level $1$ but you can finish at any level you want, can you find the minimum possible time you need to shoot all balloons in all levels and finish the game?

Input

The first line contains one integer $n$ $(1 \leq n \leq 3 \cdot 10^{5})$, which is the number of levels.  
The second line contains $n$ integers separated by spaces, the $i_{th}$ one is $a_i$ $(1 \leq a_i \leq 10^9)$, which is the number of balloons in the $i_{th}$ level.
The third line contains $n$ integers separated by spaces, the $i_{th}$ one is $b_i$ $(1 \leq b_i \leq 10^9)$, which is the number of bullets you take once you enter the $i_{th}$ level for the first time.

Output

If it is impossible to finish the game print $-1$, otherwise print the minimum total number of seconds you need to finish the game.

Notes

First sample:
once you start at level one you gain $1$ bullet, shoot the balloon at level one and move to level 2. (takes 2 seconds).
once you enter level 2 you gain $1$ bullet, shoot a balloon in level 2 and move to level 3 (takes 2 seconds).
once you enter level 3 you gain $2$ bullets, shoot the balloon in level 3 and go back to level 2 (takes 2 seconds).
shoot the balloon in level 2 and move to level $3$ then move to level $4$ (takes 3 seconds).
once you enter level 4 you gain $1$ bullet, shoot a balloon in level $4$ and move to level $5$ (takes 2 seconds).
once you enter level 5 you gain $10$ bullets, shoot $2$ balloons in level $5$ and move back to level $4$ (takes 3 seconds).
shoot the $3$ remaining balloons in level $4$ and the game ends (takes 3 seconds).
The total number of seconds you spent this way is $2 + 2 + 2 + 3 + 2 + 3 + 3 = 17$ second.

Samples

Input	Output
5 1 2 1 4 2 1 1 2 1 10 Copy	17 Copy
1 10 5 Copy	-1 Copy

Notice that if the number of balloons in all levels is more than the number of bullets in all levels then it's impossible to finish the game.
The optimal solution will look like this: the $n$ levels will be divided into $m$ segments($1 ... x_1, x_1+1 ... x_2, x_{m-1} + 1 ... n$), where for each segment the number of bullets from level $1$ to the end of the segment is equal to or greater than the number of balloons from level $1$ to the end of the segment. Zaid will start at level $1$, go all the way to level $x_1$ collecting all bullets in these levels, then go back to level $1$ then go to level $x_1$ again shooting all balloons in these levels, then he will go to level $x_1 + 1$ and do the same thing, except for the last segment where he will remain at level $x_{m-1} + 1$ and not go back to level $n$ since he can finish the game at any level.
Let's say that the last segment will start at some point $x_{m-1} + 1$, then for the rest of the segments, we don't care about where they start or end, we only care about their number, the more segments the less number of seconds needed, this can be seen by observing how the cost is calculated.
So for the overall solution, for each level $i$, we try so that the last segment is from level $i+1$ to $n$ and we have as much number of segments from level $1$ to $i$(that is the maximum number of segments such that for each segment ending at $x_j$, the number of bullets from level $1$ to $x_j$ is equal to or greater than the number of balloons from level $1$ to $x_j$).