某个小镇的集资购入了 N 台发电机，第 i 台发电机每天最多能发出 C_i 度电。镇长需要决定如何最有效地利用这些发电机的电力资源，以获得最大的经济收益。

镇上有 M 家企业，每家企业愿意以一定的单价购买一定数量的电力。第 i 家企业愿意以每度电 P_i 元的价格购买最多 Q_i 度电。镇长可以选择向多家企业出售电力，但总供电量不能超过发电量。

另一方面，还有 R 个施工队，他们愿意直接租用整台发电机，不自己发电，只是临时使用发电机本身。第 i 个施工队愿意以 R_i 元的价格租用一台发电机用一天。

镇长必须在出售电力和出租发电机之间做出平衡决策：每台发电机要么用于发电出售电力，要么整台租给施工队，不可兼得。

请你帮助镇长计算出小镇每天能够通过发电机获得的最大收入。

第一行包含三个整数 N、M 和 R。

接下来 N 行，每行一个整数 C_i，表示第 i 台发电机每天的最大发电量。

接下来 M 行，每行两个整数 Q_i、P_i，表示第 i 家企业最多愿意购买 Q_i 度电，并以每度电 P_i 元的单价购买。

最后 R 行，每行一个整数 R_i，表示第 i 个施工队愿意以 R_i 元的价格租用一台发电机用一天。

输出一个整数，表示小镇通过发电机每天能获得的最大收入。

样例 1 说明

镇长可以选择让部分发电机用于发电，部分租出：

• 如果让第 1 台和第 4 台发电机发电，总发电量为 13 度。

  • 先满足企业 1 的需求（10 度 × 25 元 = 250 元），
  • 剩余 3 度电卖给企业 3（3 × 15 元 = 45 元），
  • 发电总收入为 295 元。
• 其余三台发电机租给施工队，租金分别为 250、100、80 元，合计 430 元。
• 总收益为 295 + 430 = 725 元。

数据范围

对于 20\% 的数据，满足 1 \leq N, M, R \leq 200。

对于 100\% 的数据，满足 1 \leq N, M, R \leq 10^5，1 \leq C_i, Q_i, P_i, R_i \leq 10^6。

月赛贪心25年11月