题目描述
小 L 正在参加一年一度的算法竞赛盛会 SXCPC！
今年的比赛中一共有 $K$ 道题目。小 L 与他的队友只有 $n$ 分钟的时间解决它们。小 L 和队友的默契不太好，他们在比赛中甚至还会犯“思考已经通过的题目”这种低级错误！他们的做题策略是：第 $i$ 分钟，若编号为 $a_i$ 的题目当前的状态为“未通过”，他们就通过这道题。
小 L 的对手小 Y 不希望他通过太多题目，于是他贿赂了赛事主办方。赛事主办方给出了 $m$ 种黑幕的方案。其中第 $i$ 种方案的形式，是在第 $t(1\leq t\leq n)$ 分钟开始前将编号包含在 $[L_i,R_i]$ 的题目全部设置为“小 L 未通过”（其中 $t$ 是任意的某个时间点，只能恰好选择一种黑幕方案，黑幕只能执行 恰好一次）。
令非负整数 $b_i$ 为第 $i$ 题的难度，定义 $C_t$ 为在第 $t$ 分钟使用黑幕的情况下比赛结束后小 L 剩余状态为“未通过”的题目的 $b_i$ 总和，小 Y 的快乐值为 $(n-t+1) \times C_t$。请计算小 Y 能获得的最大快乐值是多少。
输入格式
输入的第一行三个正整数 $n,m,K$ 分别表示比赛时长、黑幕方案数以及比赛题目数量。
输入的第二行包含 $n$ 个正整数 $a_i$，含义见题目描述。
输入的第三行包含 $K$ 个正整数 $b_i$，含义见题目描述。
接下来 $m$ 行，每行两个正整数 $L_i,R_i$，含义见题目描述。
输出格式
输出一个整数表示可获得的最大快乐值。
样例
样例输入 #1
7 6 10 4 1 2 10 1 8 2 1 1 1 1 1 1 1 1 1 1 3 5 1 2 3 8 4 10 6 10 3 7
样例输出 #1
36
数据范围与约定
对于所有数据，有：
- $1\leq n,m,K\leq 10^6$
- $1\leq a_i\leq K$
- $0\leq b_i\leq 10^6$
- $1\leq L_i\leq R_i\leq K$
子任务：
| 子任务编号 | $n,M,K\leq$ | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $100$ | 无 | $5$ |
| $2$ | $1000$ | 无 | $10$ |
| $3$ | $10^4$ | 无 | $10$ |
| $4$ | $5\times 10^4$ | 无 | $5$ |
| $5$ | $10^5$ | $b_i=1$ | $10$ |
| $6$ | $10^5$ | 无 | $10$ |
| $7$ | $10^6$ | $b_i=1$ | $20$ |
| $8$ | $10^6$ | 无 | $30$ |