「FAOI-R5」喷酒大赛

> 吐火，是川剧中独一无二的神秘绝技，源于古西蜀，驰名中华梨园。变脸者以魔术般的技法，瞬息间变化脸谱，更与吐火神功的诡异结合，以显示人物内心和剧情的急剧变化及内在张力，是川剧中刻画人物最有力、最浪漫的艺术手法。表演的时候，演员嘴里含着一根管子，管子里有松香末和未完全燃尽的纸灰。（纸灰烧的火候很重要，要燃尽但又不能全燃尽）需要喷火的时候，外面点燃，演员往外吹气，这样就会有火花喷出来。 WC2025 开幕式上表演的绍剧喷火非常精彩，你虽然没有学过喷火，但是你可以喷酒。

数轴上站着 $n$ 个表演者，第 $i$ 个表演者在正整数 $i$ 的位置。每个人嘴里都含着烈酒，对于第 $i$ 个表演者，你可以给他一个金币让他表演喷酒。 在你给完钱后，没有收到钱的表演者会退场，留下的表演者会在第 $0$ 时刻朝左右中的一个方向从嘴中喷出强度为 $k_i$ 的酒。形式化地，第 $i$ 个表演者喷出的酒具有方向属性 $b_i$，你可以在令 $b_i=1$ 或 $b_i=-1$。对于 $t\in[0,a_i)$ 的第 $t$ 时刻，酒的位置 $p_{i,t}=i+t\cdot b_i$。当 $t\geq a_i$ 时，该酒消失。 表演者背面有特殊防备，正面却没有。如果某个**正整数**时刻 $t$，表演者 $i$ 喷出的酒**仍然存在**且存在留下的表演者 $j$ 使得 $p_{i,t}=j$，那么： - 若 $b_i=b_j$： - 若 $k_i=0$，表演者 $i$ 喷出的酒消失。 - 若 $k_i>0$，$k_i\gets k_i-1$，即酒的强度减一。 - 若 $b_i\neq b_j$，表演者 $j$ 被喷到酒，愤怒离场。 你想要让酒铺满数轴上 $[1,n]$ 的位置，即对于任意 $i\in[1,n]$，至少存在一对非负整数 $(j,t)$ 使得 $t$ 时刻表演者 $j$ 喷出的酒**仍然存在**且 $p_{j,t}=i$。求出在达成该条件、没有表演者愤怒离场的情况下，最小花费的金币数。

第一行一个正整数 $n$，表示表演者的个数。 第二行 $n$ 个正整数，第 $i$ 个数为 $a_i$，表示第 $i$ 个表演者喷出的酒的距离。 第三行 $n$ 个正整数，第 $i$ 个数为 $k_i$，表示第 $i$ 个表演者喷出的酒的强度。

一行一个正整数，表示覆盖 $[1,n]$ 的最小代价。

10
1 1 4 5 1 4 1 2 1 2
1 1 2 0 3 1 2 0 2 1

3

10
1 1 9 2 4 9 2 2 1 1
1 0 3 2 3 0 3 8 2 1

3

24
1 4 5 2 3 1 4 2 5 3 1 1 1 3 2 1 1 1 1 2 2 1 1 3 
1 1 4 0 3 0 0 4 0 5 3 2 0 3 2 1 0 3 2 0 0 2 1 1

10

### 样例解释 - 样例 #1：给 $3,4,10$ 三个表演者金币，令 $b_3=-1,b_4=1,b_{10}=-1$。 - 样例 #2：给 $1,2,3$ 三个表演者金币，令 $b_1=-1,b_2=-1,b_{3}=1$。 ### 数据范围与约定 **本题采用捆绑测试。** - 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）：无特殊限制。 对于所有数据，$1\leq n,a_i\leq 5\times 10^5$，$0\le k_i\le5\times10^5$。