Minimum Coin Activation for Alcohol Spray Coverage

On a number line, there are n performers standing at positions 1, 2, …, n. Each performer has a bottle of strong liquor in his mouth. You may pay a coin to a performer to have him perform a liquor-spraying act. When paid, the performer stays and at time 0 he begins to spray liquor in one chosen direction. Formally, if the i-th performer (located at position i) is activated:

• You choose his spray direction b_i which can be either $1$ (rightwards) or $-1$ (leftwards).
• The spray lasts for a_i time units: at any time t with $0 \le t < a_i$, the liquor is at position $$p_{i,t} = i + t\cdot b_i.$$ For $t \ge a_i$, the liquor disappears.

At each positive integer time t (i.e. $t\in\mathbb{Z}^+$), for every activated performer i whose liquor is still present, if there is another activated performer j located exactly at position $p_{i,t}$ then:

• If $b_i = b_j$, then a collision occurs on the front side. Specifically, if the spray’s current strength $k_i$ satisfies $k_i>0$, it is reduced by 1; but if $k_i=0$, the spray vanishes immediately.
• If $b_i \neq b_j$, then performer j is hit by the spray, gets angry, and leaves the stage – an outcome you must avoid.

Your goal is to fill every position in the interval [1, n] with liquor. That is, for every integer position i from 1 to n, there must exist some activated performer j and a nonnegative integer time t such that the liquor sprayed by performer j is still present at time t and $p_{j,t}= i$. Under the constraint that no performer becomes angry and leaves, compute the minimum number of coins you must spend.

Observation and Simplification: Note that at time 0 every activated performer covers his own position regardless of collision. Hence, a trivial (but always valid) strategy is to activate every performer at cost n. However, to minimize cost, you may try to cover several positions with a single activation. If you choose a performer with spray directed to the right ($b_i=1$), then in an isolated setting (i.e. no other activated performer in the spray’s path) his liquor will cover the interval $$[i, i+a_i-1].$$ Similarly, if you choose $b_i=-1$, his spray will cover $$[i-a_i+1, i].$$ Since collisions (between activated performers spraying in the same direction) can be avoided by an appropriate choice of performers and directions, one may view each activated performer as available in one of these two modes – each costing 1 coin and covering an interval as defined above. The problem thus reduces to selecting a subset of these intervals (each interval is available at most once per performer) whose union covers [1, n] with minimum cost.

This problem can be solved by a greedy interval covering algorithm. For each performer i (1 ≤ i ≤ n), define:

• Right‐mode interval: $$[i, \min(n, i+a_i-1)].$$
• Left‐mode interval: $$[\max(1, i-a_i+1), i].$$

Then, combine all these intervals and run a greedy algorithm: at every step, among those intervals whose start is at most the next uncovered position, select the one with the farthest end. This gives the minimum number of activations (coins) needed.

inputFormat

The input consists of three lines:

1. An integer n ($1 \le n \le 10^5$) – the number of performers.
2. n space‐separated integers: a1, a2, ..., an (each ≥ 1) representing the duration of the spray for each performer.
3. n space‐separated integers: k1, k2, ..., kn (each ≥ 0) representing the initial spray strength. (Note that an activated performer spraying in isolation does not require any spray strength to cover extra positions, since time 0 always covers his own position.)

You may assume that a solution always exists (for example, by activating every performer).

outputFormat

Output a single integer – the minimum number of coins required to cover every position in [1, n] with liquor, while ensuring no performer ever gets hit from the opposite direction (i.e. no angry departures occur).

sample

5
5 1 1 1 1
0 0 0 0 0

1