题目描述

今天是小X的生日，他肥肠高兴，买了一个蛋糕，令人震惊的是，他居然买了一块圆形蛋糕，更令人震惊的是，他把这个蛋糕切成了$n$等份的扇形块，每一块按照顺时针都有$1$到$n$的标号，第$i$块编号为$i$,也被称为第$n+i$块,初始时，每一块的颜色均为$0$。 你可以执行以下操作任意次数： 选择整数$a$,$b$,$c$,满足$1 \le a,b,c \le n$,对于每个整数$i(0 \le i < b)$,你可以将第$a+i$块的颜色改为颜色$c$,此操作的代价是$b+x_{c}$。 你的目标是将每一个第$i$块蛋糕的颜色变为$c_{i}$,并使其代价最小。

输入格式

$n$

$c_{1}$ $c_{2}$ $......$ $c_{n-1}$ $c_{n}$

$x_{1}$ $x_{2}$ $......$ $x_{n-1}$ $x_{n}$

输出格式

最小代价。

样例:

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

20

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

5000000005

提示

样例1解释: 初始时，$(A\_1, A\_2, A\_3, A\_4, A\_5, A\_6) = (0,0,0,0,0,0)。$

执行操作$(a,b,c)=(2,1,4)$后，变为$(0,4,0,0,0,0)$。 执行操作$(a,b,c)=(3,3,2)$后，变为$(0,4,2,2,2,0)$。 执行操作$(a,b,c)=(1,1,1)$后，变为$(1,4,2,2,2,0)$。 执行操作$(a,b,c)=(4,1,1)$后，变为$(1,4,2,1,2,0)$。 执行操作$(a,b,c)=(6,1,5)$后，变为$(1,4,2,1,2,5)$。

总代价为$5 + 5 + 2 + 2 + 6 = 20$。

$1 \le n \le 400$

$1 \le c_{i} \le n$

$1 \le x_{i} \le 10^{9}$