리무진

Taipei에서 IOI는 강연, 놀이, 준비, 식사 휴식, 수면 휴식, 대회로 빼곡한 일정을 시작했다. 하지만 주최 측은 모두가 원하는 일을 할 수 있도록 한 시간을 비워 두었다. 이는 팀 지도자들이 참가자들에게 전혀 대비시키지 않은 문제였다. 참가자들의 머릿속에 혼란과 무질서가 발생했고, 자유 시간이 끝났을 때 $N$명의 참가자는 대도시의 서로 다른 교차로에 흩어져 있으며 돌아가는 길을 전혀 알지 못한다. 다행히 대회 운영진은 길을 잃은 각 참가자가 정확히 어느 교차로에 있는지 확인할 수 있도록 각 참가자의 가방에 칩을 설치해 두었다.

리무진 운전사 Simon은 참가자들을 태워 한 번에 한 명씩 대회장으로 데려오는 임무를 맡았다. 당연히 그는 다음 강연이 시작되기 전까지 가능한 한 많은 참가자를 데려올 수 있는 순서로 이들을 구하고 싶다. 다음 강연은 $T$분 후에 시작된다. Taipei는 정수 좌표가 교차로이고 수직 및 수평 도로가 존재하는 무한하고 규칙적인 격자로 모델링할 수 있다. 한 교차로에서 인접한 교차로로 이동하는 데 정확히 1분이 걸린다.

Simon은 주소 $(0, 0)$에 있는 대회장에서 출발하여 첫 번째 사람에게 가서 태운 뒤 그 사람을 대회장으로 데려온다. 그런 다음 다음 사람에게 가는 식으로 계속한다. 그는 시간이 다할 때까지 이 과정을 계속하며, 따라서 한 번에 한 명만 데려올 수 있다. 참가자를 태우는 순서를 최적으로 선택한다면, $T$분 이내에 몇 명을 태워 대회장으로 데려올 수 있는가?

채점

제출한 해답은 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$20$| $N \leq 10$, $-1000 \leq x,y \leq 1000$

$2$ |$30$| $N \leq 1000$, $-10^6 \leq x,y \leq 10^6$

$3$ |$50$| 추가 제한 없음

입력의 첫째 줄에 태워야 하는 참가자의 수를 나타내는 정수 $N$ ($1 \leq N \leq 100\,000$)와 Simon에게 주어진 시간을 분 단위로 나타내는 정수 $T$ ($1 \leq T \leq 10^9$)가 주어진다.

이어서 $N$개의 줄이 주어진다. 각 참가자마다 한 줄씩 주어진다. 각 줄은 두 정수 $-10^8 \leq x, y \leq 10^8$, 즉 그 사람의 현재 위치의 $x$-좌표와 $y$-좌표로 이루어진다.

Simon이 순서를 최적으로 선택할 때 시간이 다하기 전에 대회장으로 데려올 수 있는 참가자 수를 출력한다.

예제 1에 대한 설명: Simon에게는 5분이 주어지며, 태워야 하는 참가자가 세 명 있다. 첫 번째 참가자를 데려오는 데는 4분, 두 번째 참가자를 데려오는 데는 6분, 세 번째 참가자를 데려오는 데는 4분이 걸린다(최적으로 이동하는 경우). 주어진 시간이 5분뿐이므로 한 명만 데려올 수 있다.

예제 2에 대한 설명: Simon은 아무도 데려올 수 없다.

예제 3에 대한 설명: Simon은 위치 $(-100, 0)$에 있는 사람 한 명을 간신히 데려올 수 있다.