/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
半径で切って N 等分された円形のケーキがあります。
各ピースには時計回りに 1, 2, \ldots, N の番号が付けられています。また、1 \leq i \leq N なる整数 i についてピース i をピース N + i とも呼ぶこととします。
はじめ、すべてのピースの色は色 0 です。
あなたは、以下の操作を好きな回数行うことができます。
- 1 \leq a, b, c \leq N なる整数 a, b, c を選ぶ。0 \leq i < b なる各整数 i に対してピース a + i の色を色 c に変更する。この操作にはコストが b + X_c かかる。
1 \leq i \leq N なるすべての整数 i に対してピース i の色を色 C_i にするために必要なコストの合計の最小値を求めてください。
制約
- 1 \leq N \leq 400
- 1 \leq C_i \leq N
- 1 \leq X_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N C_1 C_2 \ldots C_N X_1 X_2 \ldots X_N
出力
答えを出力せよ。
入力例 1
6 1 4 2 1 2 5 1 2 3 4 5 6
出力例 1
20
ピース i の色が色 A_i であるとします。はじめ、(A_1, A_2, A_3, A_4, A_5, A_6) = (0, 0, 0, 0, 0, 0) です。
(a, b, c) = (2, 1, 4) として操作を行うと (A_1, A_2, A_3, A_4, A_5, A_6) = (0, 4, 0, 0, 0, 0) となります。
(a, b, c) = (3, 3, 2) として操作を行うと (A_1, A_2, A_3, A_4, A_5, A_6) = (0, 4, 2, 2, 2, 0) となります。
(a, b, c) = (1, 1, 1) として操作を行うと (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 4, 2, 2, 2, 0) となります。
(a, b, c) = (4, 1, 1) として操作を行うと (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 4, 2, 1, 2, 0) となります。
(a, b, c) = (6, 1, 5) として操作を行うと (A_1, A_2, A_3, A_4, A_5, A_6) = (1, 4, 2, 1, 2, 5) となります。
このとき、コストの合計は 5 + 5 + 2 + 2 + 6 = 20 となります。
入力例 2
5 1 2 3 4 5 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 2
5000000005
入力例 3
8 2 3 3 1 2 1 3 1 3 4 1 2 5 3 1 2
出力例 3
23
Score : 550 points
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.
Input
The input is given from Standard Input in the following format:
N C_1 C_2 \ldots C_N X_1 X_2 \ldots X_N
Output
Print the answer.
Sample Input 1
6 1 4 2 1 2 5 1 2 3 4 5 6
Sample Output 1
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 2
5 1 2 3 4 5 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 2
5000000005
Sample Input 3
8 2 3 3 1 2 1 3 1 3 4 1 2 5 3 1 2
Sample Output 3
23