测试数据来自 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