만남

올해 여름, 종혁이는 친구들과 함께 락 페스티벌에 가려고 한다. 종혁이는 친구들의 티켓까지 모두 직접 구매했고, 이제 티켓을 친구들에게 배달하려고 한다.

종혁이와 친구들이 사는 마을은 이차원 평면으로 나타낼 수 있다. 종혁이는 정수 좌표 위에만 설 수 있으며, 한 걸음에 현재 위치와 인접한 여덟 좌표 중 하나로 이동할 수 있다. 즉, 위, 아래, 왼쪽, 오른쪽, 네 대각선 방향으로 이동할 수 있다.

각 친구는 티켓을 받기 위해 자기 집에서 조금 걸어 나올 수 있다. 친구의 집 좌표가 (x, y)이고 그 친구의 값이 P라면, 그 친구는 집에서 최대 P걸음 떨어진 정수 좌표까지 종혁이를 마중 나올 수 있다. P는 친구마다 다를 수 있다.

티켓을 모두 배달한 뒤, 종혁이는 실제로 어떤 순서로 친구들을 만났는지 다시 떠올렸다. 친구들을 만난 순서가 주어질 때, 종혁이가 걸어야 했던 걸음 수의 최솟값을 구하시오. 종혁이가 배달을 시작한 위치와 끝낸 위치는 알 수 없다.

첫째 줄에 친구의 수 N이 주어진다. (2 <= N <= 200,000)

다음 N개의 줄에는 친구의 집 좌표 x, y와 값 P가 주어진다. (0 <= x, y, P <= 200,000)

입력은 종혁이가 티켓을 배달하며 친구들을 만난 순서대로 주어진다.

첫째 줄에 종혁이가 모든 티켓을 배달하는 데 필요한 걸음 수의 최솟값을 출력한다.

첫 번째 공개 테스트에서는 배달을 (4, 8)에서 시작하면 첫 번째 친구를 만날 수 있다. 이후 (6, 6)으로 이동해 두 번째 친구를 만나고, (4, 5)로 이동해 세 번째 친구를 만나면 된다.