### 问题描述 $n$ 个外星 UFO 入侵了地球，你需要用防御武器摧毁这些 UFO。 $n$ 个 UFO 排成了一排，每个 UFO 有各自的类型，其中从左到右第 $i$ 个 UFO 的类型为 $c_i$。在一次操作中，你可以选择连续的 $k$ 个类型相同的 UFO 并将其摧毁，操作的花费为 $w_k$。操作结束后所有未被摧毁的 UFO 会重新排成一排，UFO 间的相对位置不变。 求摧毁全部的 UFO 需要的最小花费总和。 ### 输入格式 输入第一行包含一个整数 $n$，表示入侵的 UFO 的总数。 第二行包含 $n$ 个整数，表示数组 $c$。 第三行包含 $n$ 个整数，表示数组 $w$。 ### 输出格式 一个整数，表示摧毁全部的 UFO 需要的最小花费总和。 ### 样例输入 ```text 5 1 2 1 2 1 3 1 4 1 5 ``` ### 样例输出 ```text 5 ``` ### 说明 一种可行的操作方案为： 1. 摧毁区间 $[3,3]$ 的 UFO，区间长度为 $1$，操作的花费为 $3$。剩余的 UFO 由 $(1,2,\underline{1},2,1)$ 变为 $(1,2,2,1)$。 2. 摧毁区间 $[2,3]$ 的 UFO，区间长度为 $2$，操作的花费为 $1$。剩余的 UFO 由 $(1,\underline{2},\underline{2},1)$ 变为 $(1,1)$。 3. 摧毁区间 $[1,2]$ 的 UFO，区间长度为 $2$，操作的花费为 $1$。剩余的 UFO 由 $(\underline{1},\underline{1})$ 变为空。 操作的花费总和为 $5$。可以证明不存在使花费总和更少的操作方案。 ### 评测数据规模 对于 $40$% 的评测数据，$1\leq n \leq 16$。 对于 $100$% 的评测数据，$1\leq n \leq 100$，$1\leq c_i \leq n$，$1\leq w_i \leq 10^9$。