잠든 카멜레온

카멜레온 마을에는 $N$마리의 카멜레온이 살고 있으며, 이 마을은 2차원 평면으로 볼 수 있다. $i$번째 카멜레온은 $(X_i, Y_i)$ 위치에 있고, 색깔은 $C_i$이다.

밤이 깊었을 때 깨어 있는 것은 첫 번째 카멜레온뿐이고, 나머지 카멜레온은 모두 잠들어 있다.

갑자기 $N$번째 카멜레온에게 급한 일이 생겨서 깨워야 한다. 카멜레온을 깨우려면 몸이 직접 닿아야 한다. 따라서 다른 카멜레온이 그 위치까지 걸어가거나 혀를 뻗어 닿아야 한다.

카멜레온은 상하좌우와 대각선의 여덟 방향으로 움직일 수 있다. 구체적으로 $(x,y)$에 있는 카멜레온은 1초 만에 $(x-1,y-1)$, $(x-1,y)$, $(x-1,y+1)$, $(x,y-1)$, $(x,y)$, $(x,y+1)$, $(x+1,y-1)$, $(x+1,y)$, $(x+1,y+1)$ 중 한 곳으로 이동할 수 있다.

또한 카멜레온은 혀를 세로나 가로 방향으로 뻗을 수 있다. 즉 $(x,y)$에 있는 카멜레온은 임의의 정수 $c$에 대해 $(x+c,y)$ 또는 $(x,y+c)$에 혀를 닿게 할 수 있다. 혀를 뻗는 데는 시간이 걸리지 않는다. 다만 같은 색깔의 카멜레온끼리는 서로를 알아보기 어려워 겨냥이 힘들기 때문에, 서로를 향해 혀를 뻗을 수 없다. 혀를 뻗을 때 경로에 다른 카멜레온이 있어도 상관없다. 혀의 목적지에 있는 카멜레온만 깨어나고, 경로에 있던 다른 카멜레온은 깨지 않는다.

카멜레온은 졸음이 많아서, 다른 카멜레온을 깨운 직후 현재 자리에서 바로 다시 잠든다.

$N$번째 카멜레온을 깨우는 데 걸리는 최소 시간(초)을 구하시오.

첫째 줄에 카멜레온의 수 $N$과 색깔의 수 $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $N+1$번째 줄까지 $i+1$번째 줄에는 $i$번째 카멜레온의 초기 위치 $X_i$, $Y_i$와 색깔 $C_i$가 공백으로 구분되어 주어진다.

$N$번째 카멜레온을 깨우는 데 걸리는 최소 시간(초)을 출력한다.

• $2 \le N \le 100000$
• $1 \le M \le N$
• $-10^9 \le X_i, Y_i \le 10^9$ $(1 \le i \le N)$
• $i \neq j$이면 $X_i \neq X_j$ 또는 $Y_i \neq Y_j$이다. $(1 \le i, j \le N)$
• $1 \le C_i \le M$ $(1 \le i \le N)$
• 각 $1 \le i \le M$에 대해 $C_j = i$를 만족하는 $1 \le j \le N$이 존재한다.
• 입력의 모든 값은 정수이다.