U635144 【MX-S12-T2】区间

# 原题已添加多组hack数据，请移步[原题](https://www.luogu.com.cn/problem/P14567)。

给定三个长度为 $n$ 的正整数序列：颜色序列 $c$，权值序列 $v$，代价序列 $f$。序列的下标均由 $1$ 开始标号。保证代价序列**单调不减**，即 $f_i \le f_{i + 1}$。 对一个区间 $[l, r]$（$1 \le l \le r \le n$）做如下定义： 1. 称区间 $[l, r]$ **合法**，当且仅当：不存在一种颜色 $x$ 在区间内外均出现过，即不存在颜色 $x$ 和下标 $i, j$ 满足 $c_i = c_j = x$ 且 $i \in [l, r]$、$j \notin [l, r]$。 2. 区间 $[l, r]$ 的**价值**定义为 $\displaystyle \sum_{i = l}^{r} (v_i \cdot f_{i - l + 1})$。 找出一个价值最小的合法区间，你只需要求出该最小价值。

第一行，一个正整数 $n$。 第二行，$n$ 个正整数 $c_1, \ldots, c_n$。 第三行，$n$ 个正整数 $v_1, \ldots, v_n$。 第四行，$n$ 个正整数 $f_1, \ldots, f_n$。

输出一行，一个正整数，表示最小价值。

对于所有测试数据，保证： - $1 \le n \le 10^6$； - $1 \le f_i \le 10^3$，且 $f$ 序列单调不减； - $1 \le v_i \le 10^3$； - $1 \le c_i \le n$。 ::cute-table{tuack} | 测试点编号 | $n \le$ | $f_i \le$ | $v_i \le$ | $c_i \le$ | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1\sim 5$ | $10^3$ | $10^3$ | $10^3$ | $n$ | | $6,7$ | $10^6$ | $1$ | ^ | ^ | | $8 \sim 10$ | ^ | $5$ | ^ | ^ | | $11 \sim 15$ | ^ | $10^3$ | $1$| ^ | | $16 \sim 20$ | ^ | ^ | $10^3$ | $5$ | | $21 \sim 25$ | ^ | ^ | ^ | $n$ |