Meeting Point (Small)

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 judge how much time to set aside. Find the smallest amount of time the friends need to meet in a single city.

The map holds cities and roads. A road here is not a single link between two cities. It is a continuous route that passes through several cities in order.

Each test case gives the number of cities $N$, the number of friends $P$, and the number of roads $M$. Cities are numbered $1$ through $N$.

For each friend $i$ ($1 \le i \le P$) you get:

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

For each road $j$ ($1 \le j \le M$) you get:

• $D_j$: the distance between neighbouring cities on that road. On one road every neighbouring pair sits the same distance $D_j$ apart.
• $L_j$: the number of cities the road passes through.
• $C_{j,1}, C_{j,2}, \dots, C_{j,L_j}$: the cities the road passes through, in order. $C_{j,k}$ and $C_{j,k+1}$ are joined directly by a path of length $D_j$.

Every friend leaves at the same moment. Find the smallest time in which all of them can be in one city. If no city can hold all of them, print -1 instead of a time.

A meeting happens only in a city, and a friend who arrives early can wait for the others. No two cities are joined directly by more than one path. Once a friend reaches a city, that friend can switch between the roads passing through it at no extra cost.

The first line has the number of test cases $T$. Each test case follows in this format.

The first line holds $N$, $P$, and $M$, separated by spaces. The next $P$ lines hold $X_i$ and $V_i$. The next $M$ lines hold $D_j$, $L_j$, then $C_{j,1}$ through $C_{j,L_j}$.

Constraints

• $1 \le T \le 30$
• $1 \le N \le 110$
• $2 \le P \le 10$
• $1 \le M \le 10$
• $1 \le X_i \le N$
• $1 \le V_i \le 200$
• $1 \le D_j \le 200$
• $2 \le L_j \le 25$ and $L_j \le N$
• 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 case number starting at $1$ and $y$ is the answer for that case. If the friends cannot all meet in one city, print -1 in place of $y$.