csl找妈妈II

发布时间: 2018年12月19日 22:10   最后更新: 2018年12月30日 00:31   时间限制: 1000ms   内存限制: 128M

csl最近迷上了一款游戏,是一款闯关游戏,游戏有很多关卡,通过一些关卡可以达成一些成就。关卡都是锁定的,需要花费金币解锁,但达成一些成就可以获得金币的奖励,为了向妈妈展示他过人的技巧,他决定通过不断通关来达成更多的成就。csl想用成就奖励的金币来炫技。(游戏太难了,csl就hack了游戏开启了金币透支功能,可以在任何时候透支任何数额的金币,但为了不白费功夫,初始金币数为0,他想知道他最后最多能有多少金币)

输入样例第一行是两个整数$n$,$m$代表所有关卡数和成就项数,关卡编号$1$~$n$,第二行是$n$个整数$a_i$,代表解锁第$i$关所需要的金币。
再接下来是$m$行,描述了$m$个成就的信息:
每项成就一行,前面两个整数$c$,$d$,$c$表示这项成就奖励的金币数,$d$表示达成这项成就需要完成的关卡数,后面接着$d$个整数$b_i$,列出达成此成就需要完成的关卡编号。
$1\leq n\leq 1000$,
$1\leq m\leq 1000$,
$1\leq a_i\leq 10^6$,
$1\leq c\leq 10^6$,
$1\leq d\leq n$,
$1\leq b_i\leq n$

输出一行包含一个正数,代表csl最后能获得的最多金币数

复制
3 2
1 2 3
3 2 1 3
2 1 1
1
复制
3 3
2 3 2
3 2 1 2
4 3 1 2 3
3 3 1 2 3
3

%

graph theory

LIN