AT_cpsco2019_s2_f.Treasure Collector

在一个 $N \times N$ 的网格上，每个格子里都放着一枚硬币。我们用 $(i, j)$ 表示第 $i$ 行、第 $j$ 列的格子位置。例如，左上角的格子是 $(1, 1)$，右上角是 $(1, N)$，左下角是 $(N, 1)$，右下角则是 $(N, N)$。

你是一名擅长驾驭机器人来收集宝藏的寻宝者，决定用这些机器人来收集网格上的硬币。

网格上有 $N$ 个机器人，编号为 $1$ 到 $N$。你将会得到一个长度为 $N$ 的排列 $P$，和一个长度为 $N$ 的正整数序列 $A$。每个机器人 $i$ 的初始位置是格子 $(i, P_i)$。机器人可以一次最多携带 $A_i$ 枚硬币。

由于一次性收集大量硬币比较困难，因此你打算将所有硬币移动到机器人的初始位置中之一。目标是，让所有的硬币都聚集到某个机器人的初始位置。

每次行动需要支付 $1$ 的代价，并且你可以执行以下操作：

• 选择一个机器人，假设是 $i$。
• 指定一个方向（上下左右之一），以及一个不超过 $A_i$ 的正整数 $x$，并告知机器人。
• 机器人会按这个方向移动到相邻格子，并且如果在途中遇到硬币，就拾取硬币；这个过程将持续，直到机器人拾取了 $x$ 枚硬币。
• 拾取完硬币后，机器人将沿原路返回它的初始位置 $(i, P_i)$，并且将所有拾取的硬币放在那里。

这些机器人已经比较老旧，容易误操作，因此不能让机器人进入其他机器人已经经过的格子，或者试图移出网格范围。

请计算，最小需要多少代价，才能将所有硬币都汇集到某个初始位置。

输入以以下形式给出：

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

输出将所有硬币聚集到某个初始位置所需的最小代价。

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

样例解释 1

可以通过以下 $4$ 次操作达成目标：

• 机器人 $1$ 向下移动，$x=1$
• 机器人 $3$ 向左移动，$x=2$
• 机器人 $2$ 向上移动，$x=1$
• 机器人 $3$ 向上移动，$x=2$

样例解释 2

可以通过以下 $4$ 次操作达成目标：

• 机器人 $1$ 向下移动，$x=2$
• 机器人 $3$ 向上移动，$x=2$
• 机器人 $2$ 向上移动，$x=1$
• 机器人 $2$ 向下移动，$x=1$

本翻译由 AI 自动生成