分数: 400 点
问题陈述
你有 N 卡。上 i第一张牌,一个整数 写入 A_i 。
对于每个 j = 1, 2, ..., M 按照此顺序,您将执行一次以下操作:
操作:最多选择 B_j 卡(可能为零)。将每张所选卡上写的整数替换为 C_j.
找出写在上面的整数的最大可能和 N 卡后 M 操作。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i, C_i \leq 10^9
- 1 \leq B_i \leq N
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 ... A_N B_1 C_1 B_2 C_2 \vdots B_M C_M
输出
打印写在 N 卡后 M 操作。
示例输入 1
3 2 5 1 4 2 3 1 5
示例输出 1
14
将第二张卡上的整数替换为 5,三张卡上写的整数之和变为 5 + 5 + 4 = 14,这是最大结果。
示例输入 2
10 3 1 8 5 7 100 4 52 33 13 5 3 10 4 30 1 4
示例输出 2
338
示例输入 3
3 2 100 100 100 3 99 3 99
示例输出 3
300
示例输入 4
11 3 1 1 1 1 1 1 1 1 1 1 1 3 1000000000 4 1000000000 3 1000000000
示例输出 4
10000000001
输出可能不适合 32位整数类型。