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

题目描述

Farmer John 意识到牛奶生产的收入不足以支持农场的扩展，因此为了赚取额外收入，他推出了一项奶牛租赁服务，称为“USACOW”（发音为“Use-a-cow”）。

Farmer John 有 $N$ 头奶牛 $(1 \le N \le 100{,}000)$，每头奶牛每天可以生产一定量的牛奶。Farmer John 农场附近的 $M$ 家商店 $(1 \le M \le 100{,}000)$ 每家商店愿意以一定价格购买一定量的牛奶。此外，Farmer John 的 $R$ 个邻居 $(1 \le R \le 100{,}000)$ 每家邻居愿意以一定价格租用一头奶牛。

Farmer John 需要决定每头奶牛是用于产奶还是租给附近的农民。请帮助他计算每天可以赚取的最大金额。

输入格式

输入的第一行包含 $N$、$M$ 和 $R$。

接下来的 $N$ 行每行包含一个整数 $c_i (1 \le c_i \le 1{,}000{,}000)$，表示 Farmer John 的第 $i$ 头奶牛每天可以生产 $c_i$ 升牛奶。

接下来的 $M$ 行每行包含两个整数 $q_i$ 和 $p_i (1 \le q_i, p_i \le 1{,}000{,}000)$，表示第 $i$ 家商店愿意以每升 $p_i$ 元的价格购买最多 $q_i$ 升牛奶。 请注意，Farmer John 可以向每家商店出售任意数量的牛奶，范围从 0 到 $q_i$ 升。

接下来的 $R$ 行每行包含一个整数 $r_i (1 \le r_i \le 1{,}000{,}000)$，表示 Farmer John 的一个邻居愿意以每天 $r_i$ 元的价格租用一头奶牛。

输出格式

输出应包含一行，表示 Farmer John 通过产奶或租奶牛每天可获得的最大利润。

请注意，输出可能超过标准 32 位整数的范围，因此可能需要使用更大的整数类型，例如 C/C++ 中的 long long。

输入输出样例

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

725

##样例说明

奶牛 1 和奶牛 4 一共生产 $13$ 升牛奶。 他可以用 $10$ 升牛奶满足第一个商店的需求（单价 25 元），赚取 250 元； 还可将剩余 $3$ 升以 15 元/升卖给第二家商店，赚取 45 元； 牛奶收益共计 295 元。

其余三头奶牛应分别以 250、80、100 元出租，额外赚取 430 元。 总利润为 $295 + 430 = 725$ 元。