가장 긴 증가하는 펍 순회

Elise는 Stackköpings Tekniska Högskola(STH)에 막 입학했으며, 신입생 환영 행사의 일환으로 전통적인 펍 순회가 열린다. 펍 순회에서는 모든 학과 공간을 방문하고 각 장소에서 무언가를 마신다. Elise와 친구들은 술을 마시지 않지만, 먼 거리를 걷는 것은 좋아한다. 따라서 이들은 공간 사이를 걷는 거리가 엄격히 증가하도록 하면서 방문 횟수가 최대한 많은 순회를 계획하려 한다. 여러분의 임무는 이들이 달성할 수 있는 최대 방문 횟수를 구하는 것이다.

학과 공간들은 평면 위의 정수 좌표를 갖는 점들에 위치한다. Elise와 친구들은 두 공간 사이의 최단 거리를 따라 항상 걷는다. 거리는 일반적인 유클리드 거리, 즉 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$이다. 어느 공간에서든 출발할 수 있다. 같은 학과 공간을 여러 번 방문할 수 있으며, 각각 별도의 방문으로 센다. 단, 같은 장소를 연속으로 두 번 방문할 수는 없다.

그림은 예제 1을 나타낸다. $(1,0)$에서 출발하여 빨간색 화살표를 따라가면 $6$번 방문하는 순회가 되며, 이는 최대 방문 횟수이기도 하다.

점수

여러분의 풀이는 여러 테스트 케이스 그룹에 대해 채점된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$10$| $N \leq 3$

$2$ |$10$| $N \leq 5$

$3$ |$30$| $N \leq 200$

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

첫째 줄에 학과 공간의 수를 나타내는 정수 $N$ ($2 \leq N \leq 2000$)이 주어진다. 다음 $N$개의 줄에는 각 학과 공간의 좌표를 나타내는 두 정수 $x_i, y_i$ ($0 \leq x_i, y_i \leq 10^9$)가 주어진다.

점들 사이의 거리가 엄격히 증가할 때 Elise와 친구들이 할 수 있는 최대 방문 횟수를 나타내는 정수 하나를 출력한다.