分数: 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,这是最大值。