Choosing a meeting place (Large)

Friends who live in different cities want to gather in one place. The roads are tangled and the friends live far apart, so it is hard to tell how much time to set aside. Find the smallest time it takes for all of them to meet in one city.

The map holds cities and roads. A road here is not a single link between two cities. It is a chain of consecutive links that runs through several cities in order.

Each test case gives the following.

• $N$: the number of cities
• $P$: the number of friends
• $M$: the number of roads

Cities are numbered $1$ through $N$.

For each friend $i$, numbered $1$ through $P$, the input gives the following.

• $X_i$: the number of the city the friend starts from
• $V_i$: the time the friend takes to move a distance of $1$

For each road $j$, the input gives the following.

• $D_j$: the distance between neighbouring cities on that road. On one road every pair of neighbouring cities is the same distance $D_j$ apart.
• $L_j$: the number of cities the road runs through
• $C_{j,1}, C_{j,2}, \dots, C_{j,L_j}$: the numbers of those cities, in order

All friends leave at the same moment. Find the smallest time needed for every friend to gather in one city, and print -1 instead when no city can hold all of them.

A meeting happens only in a city, and a friend who arrives early can wait for the others.

Across all roads, a direct link between the same two cities appears at most once. On reaching a city, a friend can change between the roads that run through that city with no extra time.

The first line holds the number of test cases $T$. Each test case has the following form.

N P M
X_1 V_1
X_2 V_2
...
X_P V_P
D_1 L_1 C_{1,1} C_{1,2} ... C_{1,L_1}
D_2 L_2 C_{2,1} C_{2,2} ... C_{2,L_2}
...
D_M L_M C_{M,1} C_{M,2} ... C_{M,L_M}

Constraints

• $1 \le T \le 30$
• $1 \le N \le 10000$
• $2 \le P \le 100$
• $1 \le M \le 1000$
• $1 \le X_i \le N$
• $1 \le V_i \le 200$
• $1 \le D_j \le 200$
• $2 \le L_j \le \min(N, 150)$
• The answer for each test case is at most $2147483647$.

For each test case print one line in the form Case #x: y, where $x$ is the test case number starting from $1$ and $y$ is the answer for that case. When the friends cannot all meet in one city, print -1 in place of $y$.

The picture shows the second test case of the sample input. A square is a city, a smiling face is a friend, the solid line is road 1 with distance $1$, and the dashed line is road 2 with distance $2$.