← 返回题目列表

AtCoder · abc424_g

G. 设置列表

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

分数: 625 点

问题陈述

有一组 N 偶像:偶像 1,偶像 2, \ldots,偶像 N.
有 M 候选歌曲,编号歌曲 1,歌曲 2, \ldots,歌曲 M.
高桥想选择其中一些歌曲(可能 0)并举行现场表演。
但是,同一首歌曲最多只能选择一次。

偶像 i (1\leq i\leq N) 可以跳舞到 A_i 歌曲。
现场表演中,歌曲 j (1\leq j\leq M) 要求 B_j 偶像跳舞,(不管谁跳舞)那首歌的兴奋点 C_j.

高桥选择要表演的歌曲,并为每首选定的歌曲选择将跳舞的偶像,但不超过每个偶像允许的舞蹈次数。 找出所选歌曲的最大可能的兴奋度总和。

约束

  • 1\leq N\leq 100
  • 1\leq M\leq 100
  • 0\leq A_i\leq M
  • 0\leq B_i\leq N
  • 0\leq C_i\leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \ldots A_N
B_1 C_1
B_2 C_2
\vdots
B_M C_M

输出

输出高桥选择的歌曲的最大可能的兴奋度总和。


示例输入 1

3 3
1 1 3
1 1
2 5
3 10

示例输出 1

11

例如,他可以选择歌曲 1,3 并选择舞者如下。

  • 在歌曲中 1,唯一的偶像 3 跳舞。
  • 在歌曲中 3, 偶像 1,2,3 跳舞。

那么,偶像跳的歌曲数 1,2,3 是 1,1,2分别满足,且条件满足。 这里,所选歌曲的兴奋度总和是 1+10=11.

不可能在满足条件的情况下选择歌曲使得兴奋之和变大,所以输出 11.


示例输入 2

2 6
6 0
0 1000000000
0 1000000000
1 1000000000
1 1000000000
1 1000000000
2 1000000000

示例输出 2

5000000000

例如,他可以选择歌曲 1,2,3,4,5 并选择舞者如下。

  • 在歌曲中 1,没有人跳舞。
  • 在歌曲中 2,没有人跳舞。
  • 在歌曲中 3,唯一的偶像 1 跳舞。
  • 在歌曲中 4,唯一的偶像 1 跳舞。
  • 在歌曲中 5,唯一的偶像 1 跳舞。

那么,所选歌曲的兴奋度总和为 5000000000,这是最大值。