[2021 SCPC 1차 예선]

예약 시스템

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







이 호텔 방들은 배열 2행 열 배열 로 나타낼 수 있다. 여기서 각 방은 로 나타낸다. 

이고 또는 이고 이면, 두 방 와 은 인접하다고 한다. 

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

예약자들의 총 수는 이고, 예약자들의 전체 집합 에 대해서, 는 집합   으로 나뉜다. 다시 말해서, .

또한 임의의 두 집합 에 대해서, 이고, 모든 집합 는 적어도 5명의 예약자를 포함한다. 다시 말해서, .

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

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

각 예약자 는 스트레스 지수 를 가진다. 

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

의 페널티는 로 주어진다. 

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

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

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

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

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

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

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




그림 1

입력

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

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

이후 차례로 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 과 이 주어진다 . 

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

다음 개 줄의 번째 줄에는 집합 에 속한 예약자들의 수를 나타내는 정수 와 각각 의 예약자들의 스트레스 지수를 나타내는 개의 정수 가 주어진다 .


출력

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

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

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

입출력예

입력
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

돌아가기