4162. 兔子集团军

【题目背景】

作为都市26翼之一的R公司凭借人体复制的奇点技术成为翼中负有盛名的佣兵企业

R公司第四集团军在改组并参与烟霾战争后作为专门服务脑叶公司的集团军而存在

【题目描述】

脑叶公司支部发生了异想体出逃，R公司需要出动第四集团军的兔子队进行镇压

兔子队由 n 只排成一列的克隆“兔子”组成。

R公司可以利用W公司的空间技术折跃一只部队进入支部，但是为了控制成本，只能折跃一个区间内的兔子进行任务。

兔子根据战斗能力分成不同的种类，第 i 只兔子的种类为 ci，为了提高效率，如果一种兔子 x 参与了任务，那么所有 ci = x 的兔子 i 都要参与任务。

初始时所有兔子都处于“冬眠”状态，需要将进行任务的兔子唤醒，唤醒兔子 i 有一个代价系数 vi。

同时，连续唤醒一个区间的兔子还需要付出额外的代价，具体来说，假如唤醒 [l,r] 这个区间中的兔子，那么在唤醒兔子 i 时需要 vi * f(i - l + 1)^2 的代价。

现在，给定你 n 个兔子的种类，代价系数和额外代价，请求出出动一只兔子队的最小花费

形式化题意：

给定三个长度为 n 的序列，分别为颜色序列 c1~cn，权值序列 v1~vn 和代价序列 f1~fn。

对于一个区间，我们做如下定义：

1. 若任意一个出现在区间里的 x，所有 ci = x 的 i 都包含在区间中，则称该区间是合法的

2. 一个区间 [l,r] 的代价为 vi * f(i - l + 1)^2 的和

找出代价最小的合法区间

保证 f 不减且非负，v 非负

【输入格式】

第一行一个整数 n

第二行 n 个整数表示 c 数组

第二行 n 个整数表示 v 数组

第三行 n 个整数表示 f 数组

【输出格式】

一行一个整数表示答案

【样例输入1】

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

【样例输出1】

5

【样例输入2】

12
3 2 1 2 1 3 4 5 4 5 4 5
2 2 2 2 2 2 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 

【样例输出2】

6

【样例说明】

第一个样例中合法区间为 [5, 6]

第二个样例中合法区间为 [7, 12]

大样例

【数据规模与约定】

对于 40% 的数据满足 fi = 1

对于另外 30 % 的数据满足 n <= 5000

对于 100% 的数据满足 n <= 1e6 ci<= n

第 11 个点为 hack 数据

保证答案不爆 longlong