[2021 SCPC 1차 예선]

예약 시스템

호텔의 \(2m\)개의 방들이 아래 그림과 같은 복도 모양으로 배치되어 있다. 







이 호텔 방들은 배열 2행 \(m\)열 배열 \(C\)로 나타낼 수 있다. 여기서 각 방은 \(C[i][j]\) \((1≤i≤2,\ 1≤j≤m)\)로 나타낸다. 

\((\)\(i=i'\) 이고 \(|j-j' |=1\)\()\) 또는 \((\)\(i ≠i'\) 이고 \(j=j'\)\()\) 이면, 두 방 \(C[i][j]\) 와 \(C[i'][j']\) 은 인접하다고 한다. 

이 호텔에 묵을 계획인 예약자들이 예약 시스템을 통해서 방을 배정받으려고 한다. 

예약자들의 총 수는 \(2m\) 이고, 예약자들의 전체 집합 \(S\)에 대해서, \(S\)는 집합  \(S_1,S_2,⋯,S_n\) 으로 나뉜다. 다시 말해서, \(S=S_1∪⋯∪S_n\).

또한 임의의 두 집합 \(S_h,\ S_k\)에 대해서, \(S_h∩S_k=∅\) 이고, 모든 집합 \(S_i\) 는 적어도 5명의 예약자를 포함한다. 다시 말해서, \(|S_i |≥5,∀i\).

예약 시스템은 방 하나에 한 사람씩 배정한다. 다시 말해서, 임의의 배정 \(A\) 는 예약자들의 집합에서 방들의 집합으로 일대일 대응이다. 

또, 한 집합에 속한 예약자들은 모두 한 덩어리의 방들을 배정 받아야 한다. 한 덩어리의 방들이란 덩어리에 속한 어떤 방 두개에 대해서도, 덩어리에 속하고 인접한 방들을 통해서 이동이 가능하다는 의미이다.

각 예약자 \(a\) 는 스트레스 지수 \(w_a\)를 가진다. 

예약 시스템의 배정 \(A\) 에서, 인접한 두 방에 각각 배정된 예약자 \(a\)와 \(b\)가 서로 다른 집합에 속하면, 충돌 \(c\) 가 발생한다고 하고, 

\(c\)의 페널티는 \(p(c)=w_a+w_b\)로 주어진다. 

그러면 배정 \(A\)의 페널티 \(p(A)\)는 \(A\)에서 발생하는 모든 충돌들의 페널티 합으로 정의한다. 

예약 시스템은 페널티 \(p(A)\)를 최소화하는 배정 \(A\) 를 찾아야 한다. 

예를 들어, 호텔에 12개의 방이 있고, 12명의 예약자는 각각 6명씩 2개의 집합 \(S_1\)과  \(S_2\)로 나뉜다. 예약자들의 스트레스 지수는 모두 1이다.

방들을 2행 6열 배열 \(C\)로 나타낼 때, \(C\)의 홀수 열에 \(S_1\)에 속한 예약자들을 짝수 열에 \(S_2\)에 속한 예약자들을 배정한다면,

같은 행의 인접한 두 방 사이에 충돌이 발생하고, 각 충돌에 2의 페널티가 주어진다. 이 경우 모두 10개의 충돌이 생기고 총 20의 페널티가 주어진다. 

(물론, 이 경우는 한 덩어리 조건도 만족하지 못한다.)

이 예에서는 2개의 충돌에서 4의 페널티가 생기는 배정이 최적이다. 




그림 1

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,

이후 차례로 \(T\) 개의 테스트 케이스가 주어진다. \((1 ≤ T ≤ 67) \)

각 테스트 케이스의 첫 줄에는 두 정수 \(n\)과 \(m\)이 주어진다 \((2≤n≤20,000,\ 5≤m≤50,000)\). 

여기서, \(n\)은 예약자들의 집합의 개수이고, 호텔에 \(2m\)개 방이 있음을 나타낸다.

다음 \(n\)개 줄의 \(i\)번째 줄에는 집합 \(S_i \)에 속한 예약자들의 수를 나타내는 정수 \(l_i\) 와 각각 \(S_i \)의 예약자들의 스트레스 지수를 나타내는 \(l_i \)개의 정수 \(w_{ij}\ (j=1,…,l_i)\)가 주어진다 \((5≤l_i≤100,000,\ 1≤w_{ij}≤10,000,000,\ \sum_{i=1}^n l_i=2m)\).


출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #\(C\)”를 출력하여야 한다. 이때 \(C\)는 테스트 케이스의 번호이다.

예약시스템의 가능한 모든 배정 중 페널티가 가장 작은 배정을 찾아서 그 최소 페널티를 출력한다.

입출력예

입력
2
2 6
6 1 2 1 3 1 1
6 3 2 2 1 4 1
2 5
5 1 2 3 4 5
5 1 2 3 4 5
출력
Case #1
4
Case #2
8

돌아가기

댓글