题目描述

小 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$

子任务：