← 返回题目列表

AtCoder · abc127_d

D. 整数卡

中文机器翻译题面 查看原题

分数: 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位整数类型。