카메라 제어

ACM48은 일본에서 인기가 많은 댄스 보컬 그룹이다. 이번 겨울에 ACM48은 월드 투어 공연을 준비하고 있고, 당신은 카메라 엔지니어로 투어에 합류했다.

당신이 맡은 일은 무대 위 카메라를 제어하는 소프트웨어를 만드는 것이다. 무대는 2차원 평면으로 생각한다. 소프트웨어로 카메라를 원하는 방향으로 돌릴 수 있지만, 카메라의 위치는 바꿀 수 없다.

공연이 진행되는 동안 각 멤버는 자신의 경로를 따라 움직이면서 자신에게 배정된 파트를 부른다. 경로는 꺾인 선분으로 주어진다. 멤버는 시각 0에 첫 번째 점에서 출발하고 각 선분 위를 일정한 속력으로 움직여서 시각 $t_j$에 $j$번째 점에 도착한다. 마지막 점에 도착한 뒤에는 그 자리에 계속 머문다.

공연 내내 카메라는 멤버 한 명을 계속 잡고 있어야 한다. 시각 $t$에 카메라가 잡는 멤버를 바꾸려면 그 순간에 지금 잡고 있는 멤버와 다음에 잡을 멤버가 카메라에서 같은 방향에 있어야 한다. 즉 두 사람이 카메라를 끝점으로 하는 같은 반직선 위에 있을 때만 바꿀 수 있다.

노래하고 있는 멤버를 카메라가 잡고 있는 시간의 합이 최대가 되도록 할 때, 그 최댓값을 구한다.

다음을 가정한다.

• 시각 0에는 아무 멤버나 잡고 시작할 수 있다.
• 어떤 멤버의 경로도 카메라 위치를 지나지 않는다.
• 각 멤버는 마지막 점에 도착한 뒤 그 자리에 머문다.

입력은 여러 개의 데이터 세트로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

N
cx cy
1번 멤버의 정보
...
N번 멤버의 정보

$N$ ($1 \le N \le 50$)은 멤버 수이고, $(cx, cy)$는 카메라의 좌표이다. 그다음 $N$명의 멤버 정보가 차례로 주어진다. $i$번 멤버의 정보는 다음 형식이다.

Mi
xi,1 yi,1 ti,1
...
xi,Mi yi,Mi ti,Mi
Li
bi,1 ei,1
...
bi,Li ei,Li

$M_i$ ($1 \le M_i \le 100$)는 $i$번 멤버 경로에 있는 점의 개수이고, $(x_{i,j}, y_{i,j})$는 경로의 $j$번째 점이다. $t_{i,j}$는 $i$번 멤버가 $j$번째 점에 도착하는 시각으로, $t_{i,1} = 0$이고 $t_{i,j} < t_{i,j+1} \le 10^3$이다. $L_i$ ($0 \le L_i \le 100$)는 $i$번 멤버가 맡은 파트의 개수이고, $b_{i,k}$와 $e_{i,k}$ ($0 \le b_{i,k} < e_{i,k} < b_{i,k+1} < e_{i,k+1} \le 10^3$)는 $k$번째 파트의 시작 시각과 끝 시각이다.

입력값은 모두 정수이고, 모든 좌표의 절댓값은 $10^3$ 이하이다. $N = 0$인 줄이 나오면 입력이 끝난다. 이 줄은 데이터 세트로 처리하지 않는다.

각 데이터 세트마다 노래하는 멤버를 카메라가 잡을 수 있는 시간의 최댓값을 한 줄에 출력한다. 값은 소수점 아래 여섯째 자리까지 반올림해서 출력한다.