U634819 【MX-S12-T2】区间

**请注意本题下面小样例和原题不同，和hack 1构造相同** **目前我已知所有基于~~单调栈~~的做法大概率是错的** **对于部分双指针会使得 TLE** upd:新加入了多组数据 好像单调栈也可以 记分方式为：最小得分最大时间 upd:好像有组数据锅了，不过看来50个WA的评测记录没有挂这个点的。

给定三个长度为 $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$。