题目描述

有一个圆形蛋糕，它被半径切成了 $N$ 等份。

每块蛋糕按顺时针方向标记为从 $1$ 到 $N$ 的整数，对于每个整数 $i$，当 $1 \leq i \leq N$ 时，块 $i$ 也可以称为块 $N + i$。

最开始，每块的颜色为颜色 $0$。

你可以进行以下操作任意次数：

• 选择整数 $a$、$b$ 和 $c$，使得 $1 \leq a, b, c \leq N$。对于每个整数 $i$，当 $0 \leq i < b$ 时，将块 $a + i$ 的颜色更改为颜色 $c$。该操作的成本为 $b + X_c$。

你希望每块 $i$(对于 $1 \leq i \leq N$)的颜色为 $C _i$。找到实现这一目标所需的最小总操作成本。

输入格式

输入通过标准输入给出，格式如下：

$N$
$C_1$ $C_2$ $\ldots$ $C_N$
$X_1$ $X_2$ $\ldots$ $X_N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

20

输入输出样例 #2

输入 #2

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

输出 #2

5000000005

输入输出样例 #3

输入 #3

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

输出 #3

23

说明/提示

数据范围

• $1 \leq N \leq 400$
• $1 \leq C_i \leq N$
• $1 \leq X_i \leq 10^9$
• 输入中的所有值均为整数

样例解释 1

设 $A_i$ 表示第 $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)$。
此时总成本为 $(1 + X_4) + (3 + X_2) + (1 + X_1) + (1 + X_1) + (1 + X_5) = (1+4) + (3+2) + (1+1) + (1+1) + (1+6) = 20$。