응급실

미국에서는 많은 사람들이 의료 보험이 없어서 여러 문제가 생깁니다. 대부분의 의사는 보험이 없는 환자를 진료하지 않기 때문에, 보험이 없는 사람은 진료를 받기가 어렵습니다. 그러나 응급실은 원래의 취지상 생사를 가를 수 있는 곳이므로 모든 환자를 진료해야 합니다. 그 결과, 보험이 없는 환자를 반드시 받아 주는 유일한 곳이 응급실이다 보니, 독감이나 홍역처럼 생명에 지장이 없는 경우에도 보험이 없는 환자들이 응급실로 몰립니다. 응급실은 생사가 걸린 상황을 먼저 처리해야 하므로 이런 환자들은 곧바로 진료받지 못하고, 결국 감염병을 가진 사람들이 붐비는 응급실에서 여러 시간을 함께 기다리게 됩니다. 이것이 감염병 확산을 막는 최선의 방법인지는 분명하지 않습니다. 이 문제에서는 응급실 방문자들 사이에서 질병이 어떻게 퍼지는지를 시뮬레이션합니다.

응급실에는 좌석이 $S$개 있으며, 각 좌석의 좌표가 주어집니다. 시간에 따른 모든 환자의 도착과 퇴장 기록이 주어집니다. 도착한 환자는 그 순간 비어 있는 좌석 중 번호가 가장 작은 좌석에 앉고, 퇴장할 때까지 그 좌석에 머무릅니다. 같은 환자가 나중에 다시 방문할 수 있으며, 그때는 좌석을 새로 고릅니다.

처음에는 1번 환자만 질병에 걸려 있습니다. 두 사람이 서로 2미터 이하 거리의 좌석에 연속 20분 이상 함께 앉아 있으면 질병이 환자 $A$에서 환자 $B$로 전염됩니다(예를 들어 시각 5부터 시각 25까지는 충분하지만, 시각 5부터 시각 24까지는 부족합니다). 둘 중 한 명이라도 자리를 뜨면 함께 앉은 시간은 다시 0부터 셉니다(10분씩 두 번 나누어 앉는 것은 인정되지 않습니다).

환자는 감염되면 그 다음 날, 즉 감염 시점으로부터 1440분 뒤부터 질병을 전파하기 시작하며, 그 이후로는 영원히 전염성을 가집니다. 1번 환자는 전날 이미 감염된 것으로 보아 시각 0부터 전염성을 가집니다. 모든 과정이 끝났을 때 질병에 걸린 환자가 모두 몇 명인지 구하세요.

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

각 데이터 집합의 첫 줄에는 세 정수 $P, S, V$가 주어집니다. $1 \le P \le 1000$은 환자 수이며(처음에는 1번 환자만 감염되어 있습니다), $1 \le S \le 100$은 응급실의 좌석 수, $1 \le V \le 100000$은 환자 방문 횟수입니다.

그 다음 $S$개의 줄에는 각각 두 실수 $x_i, y_i$가 주어지며, 이는 $i$번째 좌석의 좌표(미터 단위)입니다. 이어서 $V$개의 줄이 주어지고, 각 줄에는 세 정수 $p_j, a_j, d_j$가 주어집니다. $p_j$는 $j$번째 방문을 한 환자의 번호, $a_j$는 도착 시각(분 단위, 시각 0 기준), $d_j > a_j$는 퇴장 시각입니다. 이 방문들은 도착 시각의 비내림차순으로 정렬되어 있습니다. 어떤 순간에도 응급실에 동시에 있는 환자 수가 $S$를 넘지 않도록 입력이 보장됩니다. 또한 환자 $i$가 환자 $j$의 퇴장 시각과 정확히 같은 시각에 도착하면, $j$는 이미 자리를 비운 것으로 보아 환자 $i$가 그 자리에 앉을 수 있습니다.

각 데이터 집합에 대해 한 줄에 "Data Set x:"를 출력합니다. 여기서 $x$는 데이터 집합의 번호입니다. 그 다음 줄에 과정이 끝났을 때 질병에 걸린 환자의 총수를 출력합니다. 서로 인접한 두 데이터 집합 사이에는 빈 줄을 하나 출력합니다.