贡献名单

想法	标程	数据	验题	题解
喵仔牛奶			xxxxxzy	喵仔牛奶

题目背景

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

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$ 时，$p_{i,t}=-1$。

表演者背面有特殊防备，正面却没有。如果某个非负整数时刻 $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]$ 的最小代价。

样例 #1

样例输入 #1

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

样例输出 #1

3

样例 #2

样例输入 #2

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

样例输出 #2

3

样例 #3

样例输入 #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

样例输出 #3

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_{10}=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$。