약속장소 정하기 Batch Compilation commands

서로 다른 도시에 사는 친구들이 급히 약속장소를 정하려고 한다. 하지만 길이 너무 복잡하고 서로 멀리 살아서, 어느 정도 시간 여유를 잡아야 할지 알아내기가 어렵다. 친구들이 한 곳에서 만나는 데 걸리는 최소한의 시간은 얼마인가?

약속장소를 잡기 위해 펼친 지도에는 도시와 각 도시를 잇는 도로에 대한 정보가 있다. 이것은 두 도시를 연결하는 길을 의미하는 것이 아니라, 연속된 길들의 집합으로서 여러 도시를 지나간다.

더욱 자세히 말하면, 각각의 T개의 테스트 케이스에 대해 다음과 같은 것이 주어진다.

• N: 도시의 숫자
• P: 친구의 수
• M: 도로의 숫자
• 각 도시는 순서대로 1부터 N까지의 번호가 붙여져 있다.

또한, 1부터 P까지의 번호가 붙여져 있는 각 친구 i에 대해, 다음과 같은 것이 주어진다.

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

각 도시를 잇는 도로 j에 대해서는 다음과 같은 것이 주어진다. 도로는 단순히 두 도시를 잇는 길이 아니라, 여러 도시를 순서대로 잇는 연속된 길의 모임이다.

• $ D_j $: 도로가 지나가는 도시들 사이의 거리. (한 도로 위에서, 인접한 도시 사이의 거리는 Dj로 같다.)
• $ L_{j} $: 도로가 지나가는 도시들의 숫자
• $ {C_{j,k} }$: 도로가 이어주는 도시의 번호가 순서대로 나열된다.

위의 정보들을 이용해서, 동시에 출발한 친구들이 한 도시에서 만나는 데 필요한 최소한의 시간을 구하시오. 만약 다들 모일 수 있는 도시가 없다면 '-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}$
• $N'$ $P'$ $M'$

출력 형식

각각의 테스트 케이스에 대해서, x가 1번부터 시작하는 케이스 번호라고 하고 y가 각 케이스에 해당하는 답이라고 할 때 출력 파일의 각 줄에 "Case #x: y"와 같은 형식으로 출력한다. 친구들이 한 도시에서 만나는 것이 불가능하다면, 최소 시간 대신 '-1'을 출력한다.

제한

• 각 테스트 케이스에 대한 답은 2147483647 이하이다.
• 1 ≤ T ≤ 30.
• 1 ≤ $ V_{i} $ ≤ 200.
• 1 ≤ $ D_{i} $ ≤ 200.
• 2 ≤ $ L_{j} $ ≤ N.

Small dataset (Subtask 1, 10점)

• T = 30.
• 1 ≤ N ≤ 110.
• 2 ≤ P ≤ 10.
• 1 ≤ M ≤ 10.
• 2 ≤ $ L_{j} $ ≤ 25.

Large dataset (Subtask 2, 25점)

• T = 2.
• 1 ≤ N ≤ 10000.
• 2 ≤ P ≤ 100.
• 1 ≤ M ≤ 1000.
• 2 ≤ $ L_{j} $ ≤ 150.

예제

입력

3
2 2 1
1 1
2 2
1 2 1 2
5 2 2
1 1
5 100
1 3 1 2 3
2 3 4 2 5
5 2 2
1 1
5 5
1 2 1 2
1 3 3 4 5

출력

Case #1: 1
Case #2: 3
Case #3: -1