Bike Parking

Sanne recently came up with a lucrative business idea: renting out premium bike parking at Eindhoven train station. To maximize profit, she split the bike parking slots into $N$ tiers, numbered from $0$ to $N-1$. Tier 0 is the premium tier, very close to the train platforms. Higher-numbered tiers hold worse slots. Tier $t$ has $x_t$ slots.

Users park their bikes and get their slot through an app. Each user has a subscription level and expects a slot in the matching tier. However, the terms of service do not guarantee a slot in that tier.

If a user with subscription level $s$ gets a slot in tier $t$, one of three things happens:

1. If $t < s$, the user is happy and upvotes the app.
2. If $t = s$, the user is satisfied and does nothing.
3. If $t > s$, the user is angry and downvotes the app.

Today the app has $y_0+y_1+\ldots+y_{N-1}$ users, where $y_s$ is the number of users with subscription level $s$. Help Sanne assign the users to slots. Each user gets exactly one slot. No slot can go to more than one user, but some slots may stay empty. The number of users does not exceed the number of available slots.

Sanne wants to maximize the rating of her app. Let $U$ be the number of upvotes and $D$ the number of downvotes. Maximize $U-D$.

The first line contains one integer $N$, the number of tiers or subscription levels.

The second line contains $N$ integers $x_0, x_1, \ldots, x_{N-1}$, the number of slots in each tier.

The third line contains $N$ integers $y_0, y_1, \ldots, y_{N-1}$, the number of users at each subscription level.

Output one integer, the maximum possible value of $U-D$ over all assignments of users to slots.

• $1 \leq N \leq 3 \cdot 10^5$.
• $0 \leq x_i, y_i \leq 10^9$ for $i = 0,1,\ldots,N-1$.
• $y_0+y_1+\ldots+y_{N-1} \leq x_0+x_1+\ldots+x_{N-1} \leq 10^9$.

In the first sample, you can assign the user with subscription level 0 to a tier 0 slot, assign two users of level 1 to tier 0 slots (leading to 2 upvotes), and assign the remaining level 1 user to a tier 1 slot. This leads to a rating of $2$.

In the second sample, you can assign the level 1 user to the tier 0 slot, the level 2 user to the tier 1 slot, and the level 0 user to the tier 2 slot. This gives 2 upvotes and 1 downvote, leading to a rating of $1$.

In the third sample, you can assign the level 1 user to the tier 0 slot, the level 0 user to the tier 2 slot, and the level 4 user to the tier 3 slot. This again gives 2 upvotes and 1 downvote, leading to a rating of $1$.

The fourth sample is illustrated below. You can assign the users of level 1 to slots of tiers 0, 0, 3 and 3, leading to 2 upvotes and 2 downvotes. Next, assign the users of level 2 to slots of tiers 1, 2, 3 and 3, leading to 1 upvote and 2 downvotes. This amounts to 3 upvotes and 4 downvotes, so the rating is $-1$.

In the fifth sample, you can assign everyone to a slot matching their own subscription level, so the rating is $0$.