Integer Cards

题目描述

你有 $N$ 张卡片。第 $i$ 张卡片上写着一个整数 $A_i$。 对于每个 $j = 1, 2, ..., M$，按此顺序你将执行以下操作一次： 操作：选择至多 $B_j$ 张卡片（可以为零）。将每张被选择的卡片上写的整数替换为 $C_j$。 求在 $M$ 次操作之后卡片上写的整数之和的最大可能值。

输入格式

输入从标准输入按如下格式给出： $N$ $M$ $A_1$ $A_2$ $...$ $A_N$ $B_1$ $C_1$ $B_2$ $C_2$ $\vdots$ $B_M$ $C_M$

输出格式

输出在 $M$ 次操作之后卡片上写的整数之和的最大可能值。

3 2
5 1 4
2 3
1 5

14

10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4

338

3 2
100 100 100
3 99
3 99

300

11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000

10000000001

提示

输入中的所有值均为整数。 $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$通过将第二张卡片上的整数替换为 $5$，三张卡片上写的整数之和变为 $5 + 5 + 4 = 14$，这是最大结果。
输出可能无法适合 32 位整数类型。

标签: AtCoder|abc127D

来源

AtCoder|abc127D