약속 장소 정하기 (Small)

서로 다른 도시에 사는 친구들이 한자리에 모이려고 한다. 길이 복잡한 데다 서로 멀리 떨어져 있어서 시간을 얼마나 잡아야 할지 가늠하기 어렵다. 친구들이 한 도시에 모이는 데 필요한 최소 시간을 구하라.

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

각 테스트 케이스에는 도시의 수 $N$, 친구의 수 $P$, 도로의 수 $M$이 주어진다. 도시에는 $1$번부터 $N$번까지 번호가 붙어 있다.

친구 $i$ ($1 \le i \le P$)마다 다음 값이 주어진다.

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

도로 $j$ ($1 \le j \le M$)마다 다음 값이 주어진다.

• $D_j$: 그 도로 위에서 이웃한 두 도시 사이의 거리. 한 도로 위에서는 이웃한 도시 사이의 거리가 모두 $D_j$로 같다.
• $L_j$: 그 도로가 지나가는 도시의 수.
• $C_{j,1}, C_{j,2}, \dots, C_{j,L_j}$: 도로가 지나가는 도시의 번호를 순서대로 나열한 것. $C_{j,k}$와 $C_{j,k+1}$은 길이가 $D_j$인 길로 직접 이어져 있다.

친구들은 동시에 출발한다. 모두가 한 도시에 모이는 데 필요한 최소 시간을 구하라. 모두 모일 수 있는 도시가 하나도 없다면 최소 시간 대신 -1을 출력한다.

모임은 도시에서만 이루어지고, 먼저 도착한 친구는 다른 친구를 기다릴 수 있다. 두 도시를 직접 잇는 길은 둘 이상 존재하지 않는다. 어떤 도시에 도착하면 그 도시를 지나는 도로 사이를 추가 시간 없이 자유롭게 옮겨 다닐 수 있다.

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

첫 줄에 $N$, $P$, $M$이 공백으로 구분되어 주어진다. 이어지는 $P$개의 줄에 $X_i$와 $V_i$가 주어진다. 이어지는 $M$개의 줄에 $D_j$, $L_j$, 그리고 $C_{j,1}$부터 $C_{j,L_j}$까지가 주어진다.

제한

• $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$이고 $L_j \le N$
• 각 테스트 케이스의 답은 $2147483647$ 이하이다.

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