얼룩말 무리

얼룩말은 매우 사회적인 동물이다. 말과의 다른 동물들처럼 얼룩말도 무리를 이루며, 항상은 아니지만 상당히 규칙적으로 함께 어울려 지내는 경향이 있다. 연구자들은 얼룩말 무리가 시간에 따라 어떻게 변해 가는지, 무엇이 그 변화를 일으키는지 이해하고자 한다. 이들이 활용할 수 있는 정보는 여러 시점에서 관측한 얼룩말들의 위치뿐이며, 이 관측만으로 가장 자연스러운 무리 구분을 복원하고 싶어 한다.

전제는 다음과 같다.

• (a) 어떤 얼룩말이 한 무리에 속해 있으면, 그 무리의 다른 구성원들과 가까이 지내는 경향이 있다.
• (b) 어떤 얼룩말이 한 무리에 속해 있지 않으면, 그 무리의 구성원들로부터 멀리 떨어져 지내는 경향이 있다.
• (c) 얼룩말은 자신이 속한 무리를 좀처럼 바꾸지 않는다.

이를 정확히 정의하자. 관측의 수열이 주어진다. 각 관측 시각마다 모든 얼룩말의 정확한 위치를 알 수 있으며, 두 얼룩말 사이의 거리는 유클리드(직선) 거리이다. 무리는 정확히 두 개로 나뉜다고 가정하고, 이를 두 가지 색으로 나타낸다. 각 시각마다 모든 얼룩말을 빨강 또는 파랑으로 칠해 어느 무리에 속하는지 표시한다.

전제 (c)를 반영하기 위해, 한 얼룩말이 인접한 두 시각 사이에서 색을 바꿀 때마다 $c$의 벌점을 부과한다. 전제 (a)와 (b)를 반영하기 위해, 각 시각에서 모든 얼룩말 쌍 $i$, $j$의 거리 $d(i, j)$를 살펴본다. 두 얼룩말의 색이 같으면 그 쌍에 대해 $a \cdot d(i, j)$의 벌점을, 색이 다르면 $-b \cdot d(i, j)$의 벌점(즉, 보너스)을 부과한다.

모든 시각에 대한 모든 얼룩말의 색칠이 주어지면, 전체 벌점은 모든 시각에 걸친 모든 쌍의 벌점과 모든 색 변경 벌점의 합이다. 목표는 어떤 색칠로도 얻을 수 있는 가장 작은 전체 벌점을 찾는 것이다. 색칠 자체가 아니라 이 최소 전체 벌점만 출력하면 된다.

첫 번째 줄에는 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 각각 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 두 정수 $z$와 $t$가 주어진다. $z$는 얼룩말의 수로 $2 \le z \le 10$이고, $t$는 시각의 수로 $2 \le t \le 50$이다. 다음 줄에는 음이 아닌 실수 $a$, $b$, $c$가 주어지며, 이는 벌점 계수이다. 그다음에는 얼룩말들의 위치를 나타내는 $t$개의 줄이 이어진다. 각 줄에는 $2z$개의 실수가 있으며, 위치를 $x_1\ y_1\ x_2\ y_2\ \dots\ x_z\ y_z$ 형태로 나타낸다. 첫 번째 줄은 시각 $1$에서의 위치, 두 번째 줄은 시각 $2$에서의 위치를 나타내며, 이런 식으로 계속된다.

각 데이터 집합마다 Data Set x: 줄을 출력한다. 여기서 $x$는 데이터 집합의 번호이며 $1$부터 시작한다. 다음 줄에는 시간에 걸친 어떤 색칠로 달성할 수 있는 최소 전체 벌점을 소수점 아래 정확히 두 자리로 반올림하여 출력한다. 연속한 데이터 집합 사이는 빈 줄 하나로 구분한다.