Problem Description

There is a grid of size $N \times N$, and each cell contains one coin. The position of the cell in the $ i $-th row from the top and the $ j $-th column from the left is denoted as $ (i, j) $. For example, the top-left cell is $ (1, 1) $, the top-right cell is $ (1, N) $, the bottom-left cell is $ (N, 1) $, and the bottom-right cell is $ (N, N) $.

You are a skilled treasure hunter and plan to collect the coins on this grid using robots.

There are $ N $ robots numbered from $ 1 $ to $ N $. You are given a permutation $ P $ of $ 1 $ to $ N $ and a sequence $ A $ of length $ N $ consisting of positive integers. Robot $ i $ is initially placed at position $ (i, P_i) $ and can carry up to $ A_i $ coins simultaneously.

Due to the difficulty of collecting a large number of coins at once, you decide to gather the coins at the initial positions of the robots. Your goal is to have all coins placed at one of the initial positions of the robots.

You can perform the following operation by paying a cost of $ 1 $:

• Choose one robot. Let the chosen robot be $ i $.
• Select a direction (up, down, left, or right) and a positive integer $ x $ less than or equal to $ A_i $, and communicate these to robot $ i $.
• Robot $ i $ will repeatedly move to an adjacent cell in the specified direction and collect a coin if present.
• After collecting $ x $ coins, robot $ i $ will return to its initial position $ (i, P_i) $ and place all the coins it is carrying there.

These robots are old and prone to malfunction, so you must not instruct a robot to enter a cell that another robot has previously entered or to move outside the grid.

Find the minimum cost required to have all coins placed at one of the initial positions of the robots.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the minimum cost required to have all coins placed at one of the initial positions of the robots in one line.

Sample Input and Output

Sample Input #1

3
1 2 3
1 1 2

Sample Output #1

4

Sample Input #2

3
2 3 1
2 1 2

Sample Output #2

4

Sample Input #3

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

Sample Output #3

35

Notes/Hints

Constraints

• $2 \le N \le 80$
• $1 \le P_i \le N$
• $ P $ is a permutation of $ 1 $ to $ N $.
• $1 \le A_i \le N-1$
• All inputs are integers.

Sample Explanation 1

It can be achieved with the following 4 operations:
- Robot $ 1 $, down, $ x=1 $
- Robot $ 3 $, left, $ x=2 $
- Robot $ 2 $, up, $ x=1 $
- Robot $ 3 $, up, $ x=2 $

Sample Explanation 2

It can be achieved with the following 4 operations:
- Robot $ 1 $, down, $ x=2 $
- Robot $ 3 $, up, $ x=2 $
- Robot $ 2 $, up, $ x=1 $
- Robot $ 2 $, down, $ x=1 $

见题面 Input 部分

见题面 Output 部分