题目描述

有 $N$ 台发电机，第 $i$ 台每天可发电 $C_i$ 度。每台发电机每天只能选择一种用途：向企业卖电，或出租给施工队。

有 $M$ 家企业，第 $i$ 家最多购买 $Q_i$ 度电，每度愿意支付 $P_i$ 元。发出的电可以分配给不同企业，但每家企业的购买量不能超过上限。

有 $R$ 个施工队，第 $i$ 个施工队愿意支付 $R_i$ 元租用一台发电机，每个施工队最多租一台。

求一天的最大收益。

输入格式

第一行包含三个整数 $N,M,R$。

接下来 $N$ 行，每行包含一个整数 $C_i$。

接下来 $M$ 行，每行包含两个整数 $Q_i,P_i$。

接下来 $R$ 行，每行包含一个整数 $R_i$。

输出格式

输出一个整数。

2 1 1
10
5
8 4
20

52

数据范围与提示

• $1 \le N,M,R \le 10^5$
• $1 \le C_i,Q_i,P_i \le 10^5$
• $1 \le R_i \le 10^{18}$