410. [NOI 2009]植物大战僵尸

【问题描述】

$Plants$ $vs.$ $Zombies（PVZ）$是曾经十分风靡的一款小游戏。$Plants$（植物）和$Zombies$（僵尸）是游戏的主角，其中 $Plants$ 防守，而 $Zombies$ 进攻。该款游戏包含多种不同的挑战系列，比如 $Protect$ $Your$ $Brain$、$Bowling$ 等等。其中最为经典的，莫过于玩家通过控制 $Plants$ 来防守 $Zombies$ 的进攻，或者相反地由玩家通过控制 $Zombies$ 对 $Plants$ 发起进攻。

现在，我们将要考虑的问题是游戏中 $Zombies$ 对 $Plants$ 的进攻，请注意，本题中规则与实际游戏有所不同。游戏中有两种角色，$Plants$ 和 $Zombies$，每个 $Plant$ 有一个攻击位置集合，它可以对这些位置进行保护；而 $Zombie$ 进攻植物的方式是走到植物所在的位置上并将其吃掉。

游戏的地图可以抽象为一个 $N$ 行 $M$ 列的矩阵，行从上到下用 $0$ 到 $N–1$ 编号，列从左到右用 $0$ 到 $M–1$ 编号；在地图的每个位置上都放有一个 $Plant$，为简单起见，我们把位于第 $r$ 行第$c$列的植物记为$Pr$,$c$。

$Plants$分很多种，有攻击类、防守类和经济类等等。为了简单的描述每个$Plant$，定义$Score$和$Attack$如下：

$Zombies$必须从地图的右侧进入，且只能沿着水平方向进行移动。$Zombies$攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此$Zombies$的进攻总是从地图的右侧开始。也就是说，对于第$r$行的进攻，$Zombies$必须首先攻击$Pr$,$M-1$；若需要对$Pr$,$c（0≤c<M-1）$攻击，必须将$Pr,M-1,Pr,M-2…Pr,c+1$先击溃，并移动到位置$(r,c)$才可进行攻击。

在本题的设定中，$Plants$的攻击力是无穷大的，一旦$Zombie$进入某个$Plant$的攻击位置，该$Zombie$会被瞬间消灭，而该$Zombie$没有时间进行任何攻击操作。因此，即便$Zombie$进入了一个$Plant$所在的位置，但该位置属于其他植物的攻击位置集合，则$Zombie$会被瞬间消灭而所在位置的植物则安然无恙（在我们的设定中，$Plant$的攻击位置不包含自身所在位置，否则你就不可能击溃它了）。

$Zombies$的目标是对$Plants$的阵地发起进攻并获得最大的能源收入。每一次，你可以选择一个可进攻的植物进行攻击。本题的目标为，制定一套$Zombies$的进攻方案，选择进攻哪些植物以及进攻的顺序，从而获得最大的能源收入。

【输入文件】

输入文件的第一行包含两个整数 $N$,$M$，分别表示地图的行数和列数。

接下来$N×M$行描述每个位置上植物的信息。第$r×M+c+ 1$行按照如下格式给出植物$Pr,c$的信息：第一个整数为$Score[Pr,c]$,第二个整数为集合$Attack[Pr,c]$中的位置个数$w$，接下来$w$个位置信息$（r’,c’）$，表示$Pr,c$可以攻击位置第$r’$行第$c’$列。

【输出文件】

输出文件仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为$0$。

【输入样例】

3 2

10 0

20 0

-10 0

-5 1 0 0

100 1 2 1

100 0

【输出样例】

25

【样例说明】

在样例中,植物P1,1可以攻击位置(0,0),P2, 0可以攻击位置(2,1)。

一个方案为，首先进攻P1,1,P0,1，此时可以攻击P0,0。共得到能源收益为(-5)+20+10 = 25。注意,位置(2,1)被植物P2,0保护，所以无法攻击第2行中的任何植物。

【大致数据规模】

约20%的数据满足1 ≤N,M≤ 5；

约40%的数据满足1 ≤N,M≤ 10；

约100%的数据满足1 ≤N≤ 20，1 ≤M≤ 30，-10000 ≤Score≤ 10000