약속 장소 정하기 (Large)

문제

서로 다른 도시에 사는 친구들이 한자리에 모이려고 한다. 길이 복잡하고 사는 곳이 서로 멀어서 시간을 얼마나 잡아야 할지 가늠하기 어렵다. 친구 전원이 한 도시에 모이는 데 걸리는 최소 시간을 구하시오.

지도에는 도시와 도로 정보가 있다. 여기서 도로는 두 도시를 잇는 하나의 길이 아니라, 여러 도시를 순서대로 지나는 연속된 길의 모임이다.

테스트 케이스마다 다음이 주어진다.

$N$ : 도시의 수
$P$ : 친구의 수
$M$ : 도로의 수

도시에는 $1$ 번부터 $N$ 번까지 번호가 붙어 있다.

$1$ 번부터 $P$ 번까지 번호가 붙은 친구 $i$ 마다 다음이 주어진다.

$X_i$ : 친구가 출발하는 도시의 번호
$V_i$ : 친구가 거리 $1$ 만큼 움직이는 데 걸리는 시간

도로 $j$ 마다 다음이 주어진다.

$D_j$ : 그 도로에서 이웃한 두 도시 사이의 거리. 한 도로 위에서는 이웃한 도시 사이의 거리가 모두 $D_j$ 로 같다.
$L_j$ : 그 도로가 지나는 도시의 수
$C_{j,1}, C_{j,2}, \dots, C_{j,L_j}$ : 도로가 지나는 도시의 번호를 순서대로 나열한 것

친구들은 모두 같은 시각에 출발한다. 전원이 한 도시에 모이는 데 필요한 최소 시간을 구하고, 모두가 모일 수 있는 도시가 하나도 없으면 대신 -1을 출력하시오.

모임은 도시에서만 이루어지며, 먼저 도착한 친구는 나머지 친구를 기다릴 수 있다.

두 도시를 곧바로 잇는 구간은 모든 도로를 통틀어 많아야 한 번 나타난다. 어떤 도시에 도착하면 그 도시를 지나는 도로 사이를 추가 시간 없이 자유롭게 갈아탈 수 있다.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스는 다음 형식이다.

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}

제한

$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)$
각 테스트 케이스의 답은 $2147483647$ 이하이다.

출력

각 테스트 케이스마다 한 줄씩 Case #x: y 형식으로 출력한다. $x$ 는 $1$ 부터 시작하는 테스트 케이스 번호이고, $y$ 는 그 케이스의 답이다. 친구 전원이 한 도시에 모일 수 없으면 $y$ 자리에 -1을 출력한다.

힌트

그림은 예제 입력의 두 번째 테스트 케이스를 나타낸다. 정사각형은 도시, 웃는 얼굴은 친구, 실선은 거리가 $1$ 인 1번 도로, 점선은 거리가 $2$ 인 2번 도로이다.