Problem A
Imprisoned Imps

Cordelia is playing a farming game with a 2D grid, where you are a witch planting herbs. As you progress through the game, you can summon imps that aid you during the day, picking herbs and watering them. However, during the night, the imps tend to become nasty rascals that vandalise your property. To protect your crops, you’ll have to contain them in some way.

Figure 1: Sample inputs 1 and 2, with valid solutions. Tiles from 1-Bit Pack by Kenney

One way to contain them is by imprisoning them in a lava network. A lava network is a directed acyclic graph of lava pumps connected by straight lava channels. The first lava pump pumps lava from the Earth’s core (the yellow dots in Figure ) and the last lava pump pumps lava back down into Earth’s core (purple dots). The remaining ones ensure the flow keeps going, and can distribute the incoming lava into multiple flows with varying flow rates if so desired.

Because the game is grid-based, the lava channels will always be axis-aligned. The grid also impacts the imps’ movement: An imp can only move from its current grid tile to all adjacent grid tiles, though not diagonally. And an imp moving around can be a problem, because they know how to cast frost spells. If only one manages to move onto a weak spot in the lava network, they can solidify the entire thing. If that were to happen, Cordelia’s entire farm would surely be destroyed!

More specifically, imp $i$ can solidify the entire network if they move on top of a lava pump or lava channel with a total flow that is strictly lower than its spell level $S_ i$. They are unable to move onto a grid tile where a lava pump/channel has a total flow equal to or greater than their spell level.

To ensure she can imprison them all, she has enclosed and isolated them. An imp is enclosed if it can’t move to the tile at $(-1, -1)$ without walking over a lava pump/channel, and it is isolated if it can’t move to a tile with another imp without walking over a lava pump/channel.

However, Cordelia’s not entirely sure how to figure out how fast the lava has to flow in the different sections of her lava network, so she is working on making a program to compute the lowest possible flow she can use to imprison the imps.

Input

The first line consists of two integers $I$ and $P$, the number of imps and the number of lava pumps.

Next follow $I$ lines, one for each imp. Each line contains three integers $I_{x,i}$, $I_{y,i}$ and $S_ i$, denoting the imp’s position and its spell level.

Then follow $P$ lines, one for each lava pump $p$. Each line starts with three integers: $C_{x,i}$ and $C_{y,i}$, denoting the pump’s position, and $O_ i$, denoting the number of outward flows this pump has. Then, on the same line, follows $O_ i$ integers, $V_{i,0}, V_{i,1} \ldots V_{i,O_ i-1}$. Lava pump $i$ can pump lava in a straight line from itself to all lava pumps $V_{i,j}$.

$p_0$ is the first lava pump, pumping lava up, and $p_{P-1}$ is the last, pushing lava down into Earth’s core.

Output

Assuming there is no limit to a lava channel’s flow, output the minimal required units of lava per second the first lava pump must pump up from the Earth’s core.

Limits

• $0 < I < 1000$, $3 < P < 1000$

• $0 \leq I_{x,i}, I_{y,i}, C_{x,i}, C_{y,i} \leq 1000$

• $0 < S_ i \leq 25$

• For $i \neq j$, $(C_{x,i}, C_{y,i}) \neq (C_{x,j}, C_{y,j})$

• For $i < P-1$, $0 < O_ i < 5$, and $O_{P-1} = 0$

• $0 < V_{i,j} < P$ and $V_{i,j} \neq i$

• Lava pump $i$ can pump lava in a straight line towards lava pump $V_{i,j}$. The line will be in one of the cardinal directions. All outward flows from a lava pump will be in different cardinal directions.

• All imps are enclosed and isolated as specified by the problem statement.

• The lava network is a directed acyclic graph where all segments can flow to the last pump.

2 8
1 1 2
4 1 3
0 0 2 1 4
2 0 2 2 5
3 0 2 3 7
5 0 1 6
0 2 1 5
2 2 1 7
5 2 1 7
3 2 0

10

3 12
1 1 3
5 1 2
6 3 2
0 0 2 1 7
2 0 1 6
4 2 3 8 3 4
5 2 1 11
4 4 1 10
2 4 1 4
2 2 2 5 2
0 2 1 6
4 0 1 9
7 0 1 11
7 4 1 11
7 2 0

6

2 9
2 1 1
6 2 1
0 0 2 1 4
0 3 1 2
3 3 1 3
3 1 2 4 5
3 0 1 8
5 1 1 6
5 3 1 7
7 3 1 8
7 0 0

2