问题文

有一个 $N \times N$ 的网格，每个格子上都放着一枚硬币。我们将网格的第 $i$ 行第 $j$ 列的格子记作 $(i, j)$。例如，左上角的格子是 $(1, 1)$，右上角的格子是 $(1, N)$，左下角的格子是 $(N, 1)$，右下角的格子是 $(N, N)$。

您是一名擅长机器人探险的宝藏猎人，打算使用机器人来收集这个网格上的硬币。

一共有 $N$ 台机器人，编号从 $1$ 到 $N$。给定一个 $1$ 到 $N$ 的排列 $P$ 和长度为 $N$ 的正整数序列 $A$。机器人 $i$ 最初位于位置 $(i, P_i)$，同时最多可以携带 $A_i$ 枚硬币。

由于一次性收集大量硬币很困难，您决定将硬币集中到机器人的初始位置上。您的目标是将每个硬币都放置在机器人的初始位置之一。

每支付 $1$ 的代价，您可以进行以下操作：

• 选择一个机器人。设选中的机器人为 $i$。
• 选择上下左右其中一个方向，并选择不超过 $A_i$ 的正整数 $x$，并将它们传达给机器人 $i$。
• 机器人 $i$ 沿着传达的方向移动到相邻格子上，并重复这个过程，直到移动到的格子上没有硬币为止。
• 当机器人 $i$ 收集了 $x$ 枚硬币后，它会原路返回到初始位置 $(i, P_i)$，并将手中所有的硬币放置在那里。

由于这些机器人很古老且容易发生故障，您不能让机器人进入其他机器人已经进入过的格子，也不能让机器人走出网格之外。

请计算将每个硬币都放置在机器人的初始位置之一所需的最小代价。

约束条件

• $2 \le N \le 80$
• $1 \le P_i \le N$
• $P$ 是 $1$ 到 $N$ 的排列。
• $1 \le A_i \le N-1$
• 输入均为整数。

输入

从标准输入读取以下格式的输入。

$N$ $P_1 \ P_2 \ \ldots \ P_N$ $A_1 \ A_2 \ \ldots \ A_N$

输出

输出将每个硬币都放置在机器人的初始位置之一所需的最小代价，输出为一行。

示例 1

3
1 2 3
1 1 2

输出示例 1

4

以下操作可以实现目标：

• 选择机器人 $1$，向下，$x=1$
• 选择机器人 $3$，向左，$x=2$
• 选择机器人 $2$，向上，$x=1$
• 选择机器人 $3$，向上，$x=2$

示例 2

3
2 3 1
2 1 2

输出示例 2

4

以下操作可以实现目标：

• 选择机器人 $1$，向下，$x=2$
• 选择机器人 $3$，向上，$x=2$
• 选择机器人 $2$，向上，$x=1$
• 选择机器人 $2$，向下，$x=1$

示例 3

10
7 10 6 1 8 2 9 5 4 3
2 3 3 9 1 9 5 8 1 7

输出示例 3

35