토끼와 고슴도치들

독일에는 토끼와 고슴도치에 관한 유명한 우화가 있다. 토끼가 자기가 얼마나 빠른지 끊임없이 자랑하자, 토끼와 고슴도치는 들판을 가로지르는 달리기 시합을 하기로 한다. 시합이 시작되자마자 토끼는 쏜살같이 달려가지만, 반대쪽 끝에 도착하면 고슴도치가 이미 그곳에 와 있다. 토끼는 더 빠르게 되돌아 달리지만 그곳에도 고슴도치가 먼저 와 있다. 토끼는 점점 더 빠르게 양쪽 끝을 오가지만 매번 반대쪽 끝에서 고슴도치를 만나고, 결국 지쳐 쓰러진다. 물론 고슴도치가 이긴 이유는, 반대쪽 끝에 있던 것이 사실은 그의 아내였기 때문이다. 아이들에게 이 이야기를 들려줄 때의 교훈은 대개 "잘난 체하면 망신당한다" 또는 "협동은 강하다" 정도로 여겨진다. 그러나 이 이야기가 실제로 전하는 교훈은, 속임수를 쓰면 이기기 쉽다는 것이다.

여기서는 한 마리의 토끼와 여러 마리의 고슴도치가 벌이는 더 복잡한 시합을 다룬다. 토끼의 경로는 여러 개의 직선 구간(leg)으로 이루어지며, 평면 위의 점들의 수열 $(x_1, y_1), \dots, (x_n, y_n)$ 로 주어진다. 시합의 출발점은 원점 $(0, 0)$ 이다. 토끼는 일정한 속력 $u$ 로 $(x_1, y_1)$ 까지 직선으로 달리고, 이어서 $(x_2, y_2)$ 까지 직선으로 달리며, 이런 식으로 $(x_n, y_n)$ 까지 이동한다.

고슴도치들은 (토끼와 다를 수 있는) 속력 $v$ 로 움직이며 원하는 대로 어디든 걸어 다닐 수 있다. 점수는 다음과 같이 매긴다. 토끼가 $(x_i, y_i)$ ($1 \le i \le n$) 에 도착하는 바로 그 순간에 그 지점 $(x_i, y_i)$ 위에 고슴도치가 한 마리라도 있으면 그 구간은 고슴도치들이 얻는다. 그렇지 않으면 토끼가 얻는다. 만약 고슴도치와 토끼가 정확히 같은 시각에 그 지점에 도착하면, 그 구간은 토끼가 얻는다. 고슴도치들이 한 팀으로서 얻을 수 있는 구간 수의 최댓값을 구하여라.

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

각 데이터 집합의 첫 줄에는 두 정수 $n$, $h$ 와 두 실수 $u$, $v$ 가 주어진다. $1 \le n \le 10$ 은 달려야 하는 구간의 수, $1 \le h \le 5$ 는 들판 위 고슴도치의 수이고, $u$ 는 토끼의 속력, $v$ 는 고슴도치의 속력이며 둘 다 단위는 m/s 이다.

이어서 $n$ 개의 줄이 주어지며, 각 줄에는 한 점 $(x_i, y_i)$ 의 좌표가 두 실수로 주어진다. 그다음 $h - 1$ 개의 줄이 주어지며, 각 줄에는 고슴도치 $i = 2, \dots, h$ 의 초기 좌표 $(x'_i, y'_i)$ 가 주어진다. 고슴도치 $1$ 은 항상 원점에서 출발한다. 모든 좌표의 단위는 m 이다.

각 데이터 집합에 대해, 먼저 한 줄에 "Data Set x:" 를 출력한다. 여기서 x 는 그 데이터 집합의 번호(1부터 시작)이다. 다음 줄에는 고슴도치들이 함께 얻을 수 있는 구간 수의 최댓값을 출력한다. 연속한 데이터 집합 사이에는 빈 줄 하나를 출력한다.