Description

We will consider the scenario where Zombies attack Plants in the game. Note that the rules in this problem differ from the actual game. There are two roles, Plants and Zombies. Each Plant has a set of attack positions, and it can protect those positions. A Zombie attacks a plant by stepping onto the plant’s position and eating it.

The map is modeled as an $N$-by-$M$ grid. Rows are numbered from top to bottom as $0$ to $N-1$, and columns are numbered from left to right as $0$ to $M-1$. There is a $Plant$ placed at every position on the map. For simplicity, we denote the plant at row $r$ and column $c$ as $P_{r, c}$.

There are many types of Plants, such as “attack-type,” “defense-type,” and “economy-type.” To describe each Plant, define $\operatorname{Score}$ and $\operatorname{Attack}$ as follows:

• $\operatorname{Score}(P_{r, c})$ — the energy a Zombie gains by destroying plant $P_{r, c}$.
  If $\operatorname{Score}(P_{r, c})$ is a non-negative integer, then destroying $P_{r, c}$ grants energy $\operatorname{Score}(P_{r, c})$. If it is negative, then destroying $P_{r, c}$ costs energy $-\operatorname{Score}(P_{r, c})$.

• $\operatorname{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 a Zombie attacks a plant is by moving to that plant’s position and eating it. Therefore, a Zombie attack on row $r$ always starts from the right side of the map. That is, for an attack on row $r$, the Zombies must first attack $P_{r, M-1}$. If they want to attack $P_{r, c}$ with $0 \le c < M - 1$, they must first destroy $P_{r, M-1}, P_{r, M-2}, \dots, P_{r, c+1}$ and move to position $(r, c)$ to attack.

In this problem, Plants have infinite attack power. Once a Zombie enters any plant’s attack position, that Zombie is instantly eliminated and has no time to perform any attack action. Therefore, even if a Zombie steps onto a plant’s position, if that position is in another plant’s attack set, the Zombie is instantly eliminated and the plant at that position remains unharmed. (In our setting, a plant’s attack set does not include its own position; otherwise you could never destroy it.)

The Zombies’ goal is to attack the Plants’ formation to obtain the maximum energy income. Each time, you may choose one attackable plant to attack. The objective is to design an attack plan for the Zombies, choosing which plants to attack and in what order, to maximize the total energy income.

Input Format

The first line contains two positive integers $N$ and $M$, the number of rows and columns of the map.

The next $N \times M$ lines describe the plant at each position. For $0 \le r < N$ and $0 \le c < M$, the $(r \times M + c + 1)$-th of these lines gives the information for plant $P_{r, c}$ in the following format:

The first integer is $\operatorname{Score}(P_{r, c})$, the second integer is $w$, the number of positions in $\operatorname{Attack}(P_{r, c})$, followed by $w$ positions $(r', c')$, indicating that $P_{r, c}$ can attack the position at row $r'$ and column $c'$.

Output Format

Output a single integer: the maximum energy income that can be obtained. Note that you may also choose to make no attacks, in which case the income is $0$.

3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0

25

Hint

Constraints

• For $20\%$ of the testdata, $N, M \le 5$.
• For $40\%$ of the testdata, $N, M \le 10$.
• For $100\%$ of the testdata, $1 \le N \le 20$, $1 \le M \le 30$, $-10^4 \le \operatorname{Score} \le 10^4$.

Notes

Statement modified by @syksykCCC.

Translated by ChatGPT 5