Problem Statement

There is a circular cake that has been cut into $N$ equal slices by its radii.

Each piece is labeled with an integer from $1$ to $N$ in clockwise order, and for each integer $i$ with $1 \leq i \leq N$, the piece $i$ is also referred to as piece $N + i$.

Initially, every piece’s color is color $0$.

You can perform the following operation any number of times:

• Choose integers $a$, $b$, and $c$ such that $1 \leq a, b, c \leq N$. For each integer $i$ with $0 \leq i < b$, change the color of piece $a + i$ to color $c$. The cost of this operation is $b + X_c$.

You want each piece $i$ (for $1 \leq i \leq N$) to have color $C_i$. Find the minimum total cost of operations needed to achieve this.

Constraints

• $1 \leq N \leq 400$
• $1 \leq C_i \leq N$
• $1 \leq X_i \leq 10^9$
• All input values are integers.

Sample Input 1Copy

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

Sample Output 1Copy

20

Let $A_i$ denote the color of piece $i$. Initially, $(A_1, A_2, A_3, A_4, A_5, A_6) = (0, 0, 0, 0, 0, 0)$.

Performing an operation with $(a, b, c) = (2, 1, 4)$ changes $(A_1, A_2, A_3, A_4, A_5, A_6)$ to $(0, 4, 0, 0, 0, 0)$.

Performing an operation with $(a, b, c) = (3, 3, 2)$ changes $(A_1, A_2, A_3, A_4, A_5, A_6)$ to $(0, 4, 2, 2, 2, 0)$.

Performing an operation with $(a, b, c) = (1, 1, 1)$ changes $(A_1, A_2, A_3, A_4, A_5, A_6)$ to $(1, 4, 2, 2, 2, 0)$.

Performing an operation with $(a, b, c) = (4, 1, 1)$ changes $(A_1, A_2, A_3, A_4, A_5, A_6)$ to $(1, 4, 2, 1, 2, 0)$.

Performing an operation with $(a, b, c) = (6, 1, 5)$ changes $(A_1, A_2, A_3, A_4, A_5, A_6)$ to $(1, 4, 2, 1, 2, 5)$.

In this case, the total cost is $5 + 5 + 2 + 2 + 6 = 20$.

Sample Input 2Copy

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2Copy

5000000005

Sample Input 3Copy

8
2 3 3 1 2 1 3 1
3 4 1 2 5 3 1 2

Sample Output 3Copy

23