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

---

【问题描述】

　　小H 的工厂有 \(N\) 台产品加工机器，每台机器的生产能力不同，第 \(i\) 台机器每天能生产 \(c_i\) 件产品，然后把这些产品出售给 \(M\) 个客户。当然为了赚更多的利润，小H还可把它的机器出租给其他 \(R\) 个生产商。

　　现在给出每个客户每天最多需要的产品数量 \(q_i\) 和愿意出的最高单价 \(p_i\)，小H每天可以根据需要为其提供 0 到 \(q_i\) 件产品；再给出每个租赁客户租一台机器每天愿意出的价格 \(v_i\)。

　　请你帮助小H确定每天机器是用于生产还是出租，让他能赚到更多的钱！

【输入格式】

　　第一行包含三个整数：\(N,M,R\)，它们的意义如题目描述。
　　紧接着的 \(N\) 行每一行有一个整数 \(c_i\)，表示第 \(i\) 台机器每天能加工 \(c_i\) 件产品。
　　再下面的 \(M\) 行每行有两个整数 \(q_i\) 与 \(p_i\)，表示第 \(i\) 个客户愿意每天以最高 \(p_i\) 元的单价，收购不超过 \(q_i\) 件产品。
　　最后的 \(R\) 行每行有一个整数 \(v_i\)，表示生产商 \(i\) 愿意以每天 \(v_i\) 元的价格租一台机器。

【输出格式】

　　包含仅一行。表示一天最多赚到多少钱。

【输入输出样例1】

　Input

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

　Output

725

【输入输出样例1说明】

　　小H可以按如下方案来赚取利润：
　　1,4号机器用于生产，每天能生产13件产品；然后以单价25元卖给1号客户10件产品，剩余的3件产品以15元的单价卖给3号客户，共能赚250+45=295元的利润。
　　然后，他要把另外的台机器分别以250，80和100元的价格分别出租1，2，3号生产商，每天可收租金250+80+100=430元。
　　所以小H每天可赚得250+45+430=725元的利润。

【数据说明】

　　对于 \(30\%\) 的数据，\(1 ≤ N,M,R ≤ 10\)，\(1 ≤ c_i,q_i,p_i,v_i ≤ 1000000\)
　　对于 \(50\%\) 的数据，\(1 ≤ N,M,R ≤ 1000\)，\(1 ≤ c_i,q_i,p_i,v_i ≤ 10000\)。
　　对于 \(100\%\) 的数据，\(1 ≤ N,M,R ≤ 100000\)，\(1 ≤ c_i,q_i,p_i,v_i ≤ 1000000\)。

【来源】

　　Mr.he