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 ~N~ row by ~M~ column grid. The rows are numbered ~0~ to ~N-1~ from top to bottom. The columns are numbered ~0~ to ~M-1~ 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 ~r~, column ~c~ by ~P_{r, c}~.

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 ~Score~ and ~Attack~ as follows:

~Score[P_{r, c}]~	Zombies can destroy plant ~P_{r, c}~ to obtain energy. If ~Score[P_{r, c}]~ is a nonnegative integer, then that means ~Score[P_{r, c}]~ of energy is obtained from destroying ~P_{r, c}~. Otherwise if this is a negative integer, then that means destroying ~P_{r, c}~ will cost ~-Score[P_{r, c}]~ of energy.
~Attack[P_{r, c}]~	The set of positions that plant ~P_{r, c}~'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 ~r~, zombies must first attack ~P_{r, M-1}~. To attack plant ~P_{r, c}~, they must first attack and destroy plants ~P_{r, M-1}, P_{r, M-2}, \dots, P_{r, c}~. Only until they travel to position ~(r,c)~ 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 ~N~ and ~M~, representing the number of rows and columns in the map, respectively.
The next ~N \times M~ lines will provide information about the plant at each position on the grid. Line ~r \times M + c + 1~ of the input will give information about plant ~P_{r, c}~ in the following format: The first integer on the line is ~Score[P_{r, c}]~, the second integer ~w~ is the number of positions in the set ~Attack[P_{r, c}]~. On the same line, ~w~ pairs of numbers ~(r', c')~ will follow, each indicating that the attack range of ~P_{r, c}~ includes the position at row ~r~', column ~c~'.

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 ~0~.

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 ~P_{1, 1}~ can attack position ~(0, 0)~ while plant ~P_{2, 0}~ can attack position ~(2, 1)~.
One solution is, first attack plants ~P_{1, 1}~ and ~P_{0, 1}~ before attacking plant ~P_{0, 0}~. The total energy obtained is ~(-5) + 20 + 10 = 25~.

Note: position ~(2, 1)~ is protected by plant ~P_{2, 0}~, so it is not possible to attack any plant in row ~2~.

Constraints

About 20% of the test cases satisfy ~1 \le N, M \le 5~.
About 40% of the test cases satisfy ~1 \le N, M \le 10~.
About 100% of the test cases satisfy ~1 \le N \le 20~, ~1 \le M \le 30~, ~-10\,000 \le Score \le 10\,000~.

Problem translated to English by Alex.