[NOI2009]植物大战僵尸

Plants vs. Zombies（PVZ，植物大战僵尸）是一款以植物与僵尸对抗为主题的游戏。植物负责防守，僵尸负责进攻。游戏包含多种挑战模式，而本题考虑的是僵尸向植物发起进攻的情形。请注意，本题中的规则与实际游戏有所不同。

游戏地图可以抽象为一个 $N$ 行 $M$ 列的矩阵。行从上到下编号为 $0$ 至 $N-1$ ，列从左到右编号为 $0$ 至 $M-1$ 。地图上的每个位置都放有一株植物，位于第 $r$ 行、第 $c$ 列的植物记为 $P_{r,c}$ 。

每株植物具有以下两个属性：

$\operatorname{Score}[P_{r,c}]$ ：僵尸击溃植物 $P_{r,c}$ 后获得的能源。若其值为非负整数，则击溃该植物可以获得相应数量的能源；若其值为负数，则击溃该植物需要消耗 $-\operatorname{Score}[P_{r,c}]$ 的能源。
$\operatorname{Attack}[P_{r,c}]$ ：植物 $P_{r,c}$ 能够攻击的位置集合。

僵尸必须从地图右侧进入，并且只能沿水平方向移动。僵尸攻击植物的唯一方式是走到该植物所在的位置并将其吃掉。

因此，对于第 $r$ 行，僵尸必须首先攻击 $P_{r,M-1}$ 。如果要攻击 $P_{r,c}$ ，其中 $0\le c<M-1$ ，则必须先依次击溃 $P_{r,M-1},P_{r,M-2},\ldots,P_{r,c+1}$ ，之后移动到位置 $(r,c)$ ，才能攻击 $P_{r,c}$ 。

本题中，植物的攻击力是无穷大的。一旦僵尸进入某株植物的攻击位置，该僵尸会被瞬间消灭，无法进行任何攻击操作。因此，即使僵尸已经进入一株植物所在的位置，只要该位置属于其他尚未被击溃的植物的攻击位置集合，僵尸仍会被瞬间消灭，而当前位置的植物不会受到伤害。每株植物的攻击位置集合都不包含其自身所在的位置。

每次行动时，你可以选择一株当前可以进攻的植物并将其击溃。请制定僵尸的进攻方案，决定攻击哪些植物以及攻击顺序，使最终获得的能源收入最大。

你也可以不进行任何攻击，此时能源收入为 $0$ 。

输入格式

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

接下来 $N\times M$ 行按照从上到下、从左到右的顺序描述每株植物的信息。其中，第 $r\times M+c+1$ 行描述植物 $P_{r,c}$ 。

每株植物的信息首先包含两个整数 $\operatorname{Score}[P_{r,c}]$ 和 $w$ ，分别表示击溃该植物所获得的能源，以及集合 $\operatorname{Attack}[P_{r,c}]$ 中的位置数量。随后给出 $w$ 对整数 $(r',c')$ ，表示植物 $P_{r,c}$ 可以攻击第 $r'$ 行、第 $c'$ 列的位置。

输出格式

输出一个整数，表示僵尸可以获得的最大能源收入。

样例输入

样例输出

样例解释

一种可行方案是依次进攻 $P_{1,1}$ 和 $P_{0,1}$ ，此时便可以继续攻击 $P_{0,0}$ 。

获得的能源收入为：

(-5)+20+10=25

位置 $(2,1)$ 被植物 $P_{2,0}$ 保护，因此无法攻击第 $2$ 行中的任何植物。

数据范围

$1\le N\le 20$ ；
$1\le M\le 30$ ；
对于每株植物， $-10^4\le \operatorname{Score}[P_{r,c}]\le 10^4$ 。

来源与许可

本题为 NOI 2009 试题「植物大战僵尸」，题面与测试数据整理自 BZOJ。

样例 1

输入