問題文

N \times N のグリッドがあり、各マスにコインが 1 つずつ置いてあります。 グリッドの上から 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 払うたびに以下の操作を行えます。

• ロボットを 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
• 入力はすべて整数である。

入力例 1

3
1 2 3
1 1 2

出力例1

4

以下の 4 回の操作で達成できます。

• ロボット 1、 下、 x=1
• ロボット 3、 左、 x=2
• ロボット 2、 上、 x=1
• ロボット 3、 上、 x=2

入力例 2

3
2 3 1
2 1 2

出力例2

4

以下の 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