National Olympiad in Informatics, China, 2009
Plants vs. Zombies (PvZ) is currently a very popular video game. Plants and Zombies are the main roles of the game. In the game, plants defend while zombies attack. This game contains many types of different challenge modes, including "Protect Your Brains", "Bowling", etc. The most classic of them all involves the player controlling the plants to defend the attack of the zombies, or contrarily to have the player control the attack of the zombies on the plants.
Now, our problem will concern the attack of the zombies on the plants. Please note, the rules used in this problem are not identical to those in the actual game. There are two roles, plants and zombies. Each plant has a set of attackable positions and will be able to provide defense to these positions. Each zombie's attack method is to walk to the positions where plants are located and eat them up.
The game's map can be represented as an row by column grid. The rows are numbered to from top to bottom. The columns are numbered to from left to right. A plant will be positioned at every cell on the grid for simplicity's sake, and we shall refer to the plant in row , column by .
There are many types of plants, including attack types, defense types, money producing types, and so forth. To simplify the description of each plant, we define and as follows:
Zombies can destroy plant to obtain energy. If is a nonnegative integer, then that means of energy is obtained from destroying . Otherwise if this is a negative integer, then that means destroying will cost of energy. | |
The set of positions that plant 's attack range spans for defense against zombie attacks. |
Zombies must enter from the right side of the map, and can only walk horizontally across it. The only way that zombies can attack is to walk to the locations of the plants and eat them. Thus, Zombies will always start attacking from the right side. In other words, for attacks in row , zombies must first attack . To attack plant , they must first attack and destroy plants . Only until they travel to position can they start the attack on the plant there.
For the purposes of this problem, the attack power of plants is infinitely large. As soon as zombies enter the attack range of a plant, they will be instantly wiped out, and will not be given any time to perform any attack operations. Thus if a zombie were to enter a position occupied by a plant, but that position intersects with the attack range of some other plant(s), then the zombie will be instantly destroyed, leaving the plant at this position completely unharmed (in our setup, the attack range of a plant does not include its own position, or else no plants can ever be destroyed).
The objective of zombies is to attack plants on the field to obtain the greatest energy income. At each step, you can select an existing plant and initiate an attack. The objective of this problem is, design a zombie attacking scheme by selecting the order of specific plants to attack, such that the final energy income is as large as possible.
Input Specification
The first line contains two integers and , representing the
number of rows and columns in the map, respectively.
The next lines will provide information about the plant at each
position on the grid. Line of the input will give
information about plant in the following format: The first
integer on the line is , the second integer is
the number of positions in the set . On the same
line, pairs of numbers will follow, each indicating that
the attack range of includes the position at row ', column
'.
Output Specification
Output a single integer, the maximum energy income that can be obtained by the zombies.
Note: you may also choose to not initiate any attacks, which will result in an energy income of .
Sample Input
3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0
Sample Output
25
Explanation
In the sample, plant can attack position while plant
can attack position .
One solution is, first attack plants and before
attacking plant . The total energy obtained is .
Note: position is protected by plant , so it is not possible to attack any plant in row .
Constraints
About 20% of the test cases satisfy .
About 40% of the test cases satisfy .
About 100% of the test cases satisfy , , .
Problem translated to English by .
Comments