P11331 [NOISG 2022 Finals] Fruits

超市里通常有专门的一区卖水果。 兔子 $\text{Benson}$ 常去的超市一共有 $N$ 个柜台用来卖 $N$ 种水果。柜台编号从 $1 \sim N$，水果编号从 $1 \sim N$。第 $i$ 种水果的美味度是 $i$，购买需要花费 $C_i$ 元。**保证对于所有的 $1 \le i < j \le N$，有 $C_i \le C_j$。** 每一个柜台都只买一种水果，每一种水果都有且仅有一个柜台售卖。现在，工作人员规定了每个柜台卖哪一种水果。第 $i$ 个柜台卖第 $A_i$ 种水果。如果 $A_i=-1$，则表示这个柜台还没有确定卖什么。 当所有柜台的水果都摆放好，$\text{Benson}$ 就会进店抢购。他会按照 $1 \sim N$ 的顺序去这些柜台。当他到了一个柜台，如果他的购物车里还是空的，或当前柜台水果的美味度大于所有他购物车里的水果，那么他就会购买这种水果，将其放进购物车中。 现在你需要让商店赚到最多的钱。你需要计算怎么来摆放那些 $A_i=-1$ 的柜台使得利润最大化。由于 $\text{Benson}$ 很赶时间，他可能不会逛完所有柜台，所以你需要对于所有的 $1 \le k \le N$ 计算如果 $\text{Benson}$ 只逛第 $1 \sim k$ 个柜台，那么这些柜台应该如何摆放最优。

第一行，一个正整数 $N$； 第二行 $N$ 个整数，表示 $A_i$； 第三行 $N$ 个整数，表示 $C_i$。

一行 $N$ 个整数，第 $k$ 个表示如果 $\text{Benson}$ 只逛前 $k$ 个柜台且水果按照最优方案摆放，商店可获得的最大钱数。

**【数据范围】** |$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$0$|$0$|样例| |$1$|$6$|$N\le8$| |$2$|$5$|对于所有 $1\le j\le N$，$A_j=-1$| |$3$|$11$|$N\le200$| |$4$|$13$|$N\le2000$| |$5$|$23$|对于所有 $1\le j\le N$，$C_j=1$| |$6$|$42$|无| 对于 $100\%$ 的数据，$1 \le N \le 400000,1 \le A_j \le N$ 或 $A_j=-1,1 \le C_i \le 10^9$。