测试数据来自 system/2162

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

【题目描述】

　　小H的工厂共有 $n$ 台机器，这些机器可以用于加工产品赚取利润，也可以用于出租赚取租金：

　　1）第 $i$ 台机器每天的可加工 $a[i]$ 件产品；
　　2）工厂每天收会到 $m$ 个订单，其中第 $i$ 个订单准备以 $p[i]$ 元的单价购买 $q[i]$ 件产品；
　　3）有 $k$ 个商家想租借机器，其中第 $i$ 个商家愿意以每天 $r[i]$ 元的价格租借一台机器。

　　那么小H应怎样分配这些机器才能赚取更多的利润呢？

【输入格式】

　　第一行包含 $n,m,k$ 三个整数。
　　接下来的 $n$ 行，每行一个整数 $a[i]$，表示第 $i$ 台机器每天加工的产品数目。
　　再下面的 $m$ 行每行有两个整数 $q[i]$ 与 $p[i]$，表示第 $i$ 个订单想以 $p[i]$ 元的单价购买 $q[i]$ 件产品。
　　最后的 $k$ 行每行有一个整数 $r[i]$，表示第 $i$ 个商家想以每天 $r[i]$ 元的的价格租借一台机器。

【输出格式】

　　一个整数，表示小H每天最多获得多少利润。

【输入输出样例】

　Input

5 3 4
6
2
4
7
1
10 25
2 10
15 15
250
80
100
40 

　Output

725

【输入输出样例解释】

　　第 1 台和第 4 台机器用于加工产品，每天可加工 13 件产品，其中的 10 件产品满足第 1 个订单，共赚取 10 * 25 元利润。然后把剩下的 3 件产品按 15 元的单价卖给第 3 张订单，共 3 * 15 元的利润。 然后把其他3台机器分别以 250元/天，80元/天，和 100元/天价格出租给前面三个商家。最后小H一共可得利润 10*25 + 3*15 + (250+80+100) = 725 元。

【数据限制】

　　对于 $100\%$ 的数据，$1≤n,m,k≤100,000$，$1≤a[i],p[i],q[i],r[i]≤1,000,000$。

【来源】

　　Mr.he