P11656 "FAOI-R5" Liquor Spraying Contest

> Fire spitting is a unique and mysterious stunt in Sichuan opera. It originated in ancient Western Shu and is famous across the Chinese opera world. Face-changing performers use magic-like skills to switch masks in an instant, and when combined with the strange art of fire spitting, it shows sharp changes in characters’ emotions and the plot, creating strong inner tension. This is one of the most powerful and romantic ways Sichuan opera portrays characters. During a performance, the actor holds a tube in their mouth. Inside the tube there is pine resin powder and paper ash that has not been completely burned out. (How much it is burned matters a lot: it must be burned out, but not fully burned out.) When fire is needed, it is lit from the outside, and the actor blows outward, making sparks spray out. The Shaoxing opera fire-spitting show at the opening ceremony of WC2025 was amazing. Even though you have not learned fire spitting, you can spray liquor.

There are $n$ performers standing on a number line. The $i$-th performer stands at position $i$, where $i$ is a positive integer. Everyone holds strong liquor in their mouth. For the $i$-th performer, you may give them one coin to make them perform liquor spraying. After you pay, performers who did not receive money leave the stage. The remaining performers, at time $0$, spray liquor from their mouths toward either left or right with intensity $k_i$. Formally, the liquor sprayed by performer $i$ has a direction attribute $b_i$, and you may set $b_i=1$ or $b_i=-1$. For time $t\in[0,a_i)$, at time $t$ the liquor’s position is $p_{i,t}=i+t\cdot b_i$. When $t\geq a_i$, the liquor disappears. Performers have special protection on their backs, but not on their fronts. If at some **positive integer** time $t$, the liquor sprayed by performer $i$ **still exists** and there exists a remaining performer $j$ such that $p_{i,t}=j$, then: - If $b_i=b_j$: - If $k_i=0$, the liquor sprayed by performer $i$ disappears. - If $k_i>0$, then $k_i\gets k_i-1$, i.e. the liquor’s intensity decreases by $1$. - If $b_i\neq b_j$, then performer $j$ gets sprayed by the liquor and angrily leaves. You want the liquor to cover the positions $[1,n]$ on the number line. That is, for every $i\in[1,n]$, there exists at least one pair of nonnegative integers $(j,t)$ such that at time $t$ the liquor sprayed by performer $j$ **still exists** and $p_{j,t}=i$. Find the minimum number of coins needed, under the conditions that this goal is achieved and no performer leaves angrily.

The first line contains a positive integer $n$, denoting the number of performers. The second line contains $n$ positive integers. The $i$-th number is $a_i$, denoting the distance the $i$-th performer’s liquor can spray. The third line contains $n$ positive integers. The $i$-th number is $k_i$, denoting the intensity of the $i$-th performer’s liquor.

Output one positive integer in one line, denoting the minimum cost to cover $[1,n]$.

### Sample Explanation - Sample #1: Give coins to performers $3,4,10$, and set $b_3=-1,b_4=1,b_{10}=-1$. - Sample #2: Give coins to performers $1,2,3$, and set $b_1=-1,b_2=-1,b_{3}=1$. ### Constraints and Notes **This problem uses bundled testdata.** - Subtask 1 (20 pts): $n\leq 14$. - Subtask 2 (10 pts): $n\leq 50$, $k_i=0$. - Subtask 3 (15 pts): $n\leq 50$. - Subtask 4 (20 pts): $n\leq 10^3$. - Subtask 5 (15 pts): $n\leq 10^5$. - Subtask 6 (20 pts): no special restrictions. For all testdata, $1\leq n,a_i\leq 5\times 10^5$, $0\le k_i\le5\times10^5$. Translated by ChatGPT 5