Plants vs. Zombies (PVZ) is a very popular game. Plants and Zombies are the main characters, with Plants defending and Zombies attacking. The game includes various challenge series, such as Protect Your Brain, Bowling, etc. The most classic mode involves players controlling Plants to defend against Zombie attacks, or conversely, players controlling Zombies to attack Plants.
In this problem, we consider the attack of Zombies on Plants. Please note that the rules here differ from the actual game. There are two types of characters, Plants and Zombies. Each Plant has a set of attack positions that it protects. Zombies attack plants by moving to the position where the plant is located and eating it.
The game map can be abstracted as an $N \times M$ matrix, with rows numbered from $0$ to $N-1$ from top to bottom, and columns numbered from $0$ to $M-1$ from left to right. There is a Plant at every position on the map. For simplicity, we denote the plant at row $r$ and column $c$ as $P_{r,c}$.
Plants come in many types, such as offensive, defensive, and economic. To describe each Plant simply, we define $Score$ and $Attack$ as follows:
$Score[P_{r,c}]$: The energy obtained by defeating plant $P_{r,c}$. If $Score[P_{r,c}]$ is a non-negative integer, it represents the energy gained by defeating $P_{r,c}$. If it is negative, it represents the energy cost required to defeat $P_{r,c}$ (i.e., $-Score[P_{r,c}]$).
$Attack[P_{r,c}]$: The set of positions that plant $P_{r,c}$ can attack.
Zombies must enter from the right side of the map and can only move horizontally. The only way for Zombies to attack a plant is to walk to the position where the plant is located and eat it. Therefore, a Zombie's attack always starts from the right side of the map. That is, for an attack on row $r$, Zombies must first attack $P_{r, M-1}$. If an attack on $P_{r,c}$ ($0 \le c < M-1$) is required, $P_{r, M-1}, P_{r, M-2}, \dots, P_{r, c+1}$ must be defeated first, and the Zombie must move to position $(r, c)$ before it can attack.
In this problem's setting, the attack power of Plants is infinite. Once a Zombie enters a position attacked by a Plant, that Zombie is instantly destroyed, and the Zombie has no time to perform any attack operations. Therefore, even if a Zombie enters a position where a Plant is located, if that position belongs to the attack set of another plant, the Zombie will be instantly destroyed, and the plant at that position will remain unharmed (in our setting, a Plant's attack set does not include its own position; otherwise, you could never defeat it).
The goal of the Zombies is to attack the Plants' positions and obtain the maximum energy income. Each time, you can choose an attackable plant to attack. The goal of this problem is to formulate a plan for the Zombies, choosing which plants to attack and in what order, to obtain the maximum energy income.
Input
The first line contains two integers $N$ and $M$, representing the number of rows and columns of the map, respectively.
The next $N \times M$ lines describe the information for the plant at each position. The $(r \times M + c + 1)$-th line gives the information for plant $P_{r,c}$ in the following format: the first integer is $Score[P_{r,c}]$, the second integer is the number of positions $w$ in the set $Attack[P_{r,c}]$, followed by $w$ position pairs $(r', c')$, indicating that $P_{r,c}$ can attack the position at row $r'$ and column $c'$.
Output
The output contains a single integer, representing the maximum energy income that can be obtained. Note that you can also choose not to perform any attacks, in which case the energy income is 0.
Examples
Input 1
3 2 10 0 20 0 -10 0 -5 1 0 0 100 1 2 1 100 0
Output 1
25
Note 1
In the example, plant $P_{1,1}$ can attack position $(0,0)$, and $P_{2,0}$ can attack position $(2,1)$.
One plan is to first attack $P_{1,1}$, then $P_{0,1}$, at which point $P_{0,0}$ can be attacked. The total energy gain is $(-5) + 20 + 10 = 25$. Note that position $(2,1)$ is protected by plant $P_{2,0}$, so it is impossible to attack any plants in row 2.
Constraints
Approximately 20% of the data satisfies $1 \le N, M \le 5$; Approximately 40% of the data satisfies $1 \le N, M \le 10$; Approximately 100% of the data satisfies $1 \le N \le 20$, $1 \le M \le 30$, $-10000 \le Score \le 10000$.