가장 긴 증가 펍 순회

Elise는 Stackköpings Tekniska Högskola(STH)에 막 입학했다. 신입생 환영 행사의 일환으로 전통적인 펍 순회가 열린다. 펍 순회는 모든 섹션 공간을 방문하고 각 장소에서 음료를 한 잔씩 마시는 것이다. Elise와 친구들은 술을 마시지 않지만 먼 거리를 걷는 것을 좋아한다. 그래서 두 장소 사이를 걷는 거리가 엄격하게 증가하는 순회 경로를 짜서 방문 횟수를 가능한 한 많이 만들려고 한다. 그들이 달성할 수 있는 최대 방문 횟수를 구하라.

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

$(1,0)$에서 출발해 빨간 화살표를 따라가면 방문 6번의 순회가 되며, 이것이 최대이기도 하다.

첫 줄에는 섹션 공간의 개수 $N$이 주어진다 ($2 \leq N \leq 2000$). 이후 $N$개의 줄에 각 섹션 공간의 좌표 $x_i, y_i$가 정수로 주어진다 ($0 \leq x_i, y_i \leq 10^9$).

거리가 엄격하게 증가하는 순회에서 Elise와 친구들이 할 수 있는 최대 방문 횟수를 정수 하나로 출력한다.