← 返回题目列表

Codeforces · 1295/E

E. 排列分离

中文机器翻译题面 查看原题

给你一个排列 $$$p_1, p_2, \dots , p_n$$$ (一个数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次)。此排列的第 $$$i$$$ 个元素的权重为 $$$a_i$$$。

首先,将排列分成两个非空集合 - 前缀和后缀。更正式地说,第一组包含元素 $$$p_1、p_2、\dots 、p_k$$$,第二组包含元素 $$$p_{k+1}、p_{k+2}、\dots 、p_n$$$,其中 $$$1 \le k < n$$$。

之后,您可以在集合之间移动元素。您可以执行的操作是选择第一组中的某个元素并将其移动到第二组,反之亦然(从第二组移动到第一组)。您必须支付 $$$a_i$$$ 美元才能移动元素 $$$p_i$$$。

您的目标是使第一组的每个元素都小于第二组的每个元素。请注意,如果其中一组为空,则满足此条件。

例如,如果 $$$p = [3, 1, 2]$$$ 且 $$$a = [7, 1, 4]$$$,则最佳策略是:将 $$$p$$$ 分成两部分 $$$[3, 1]$$$ 和 $$$[2]$$$,然后将 $$$2$$$ 元素移入第一组(成本为$$$4$$$)。而如果$$$p = [3, 5, 1, 6, 2, 4]$$$, $$$a = [9, 1, 9, 9, 1, 9]$$$,那么最优策略是:将$$$p$$$分成两部分$$$[3, 5, 1]$$$和$$$[6, 2, 4]$$$,然后移动$$$2$$$-元素进入第一组(它花费$$$1$$$),$$$5$$$-元素进入第二组(它也花费$$$1$$$)。

计算您必须花费的最低金额。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 排列的长度。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots , p_n$$$ ($$$1 \le p_i \le n$$$)。保证该序列包含从 $$$1$$$ 到 $$$n$$$ 的每个元素恰好一次。

第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

输出

打印一个整数 — 您必须花费的最少美元数。

示例

输入 #1

3
3 1 2
7 1 4

输出 #1

4

输入 #2

4
2 4 1 3
5 9 8 3

输出 #2

3

输入 #3

6
3 5 1 6 2 4
9 1 9 9 1 9

输出 #3

2