[문제 요약] 미르코는 공연티켓을 모든 친구에게 전해 주어야 한다.

아래 입력은

3
3 10 2
8 4 2
2 5 2

좌표 상 8(상하좌우 대각선) 방향으로 움직일 수 있을 때 미르코가 모든 티켓을 전달하기 위한 최소 거리를 출력하는게 문제. 시작 위치는 임의의 지점에서 가능.

Mirko's neighbourhood can be represented by a Cartesian plane. While walking, Mirko is stepping only on lattice (integer-coordinates) points of that plane. He takes a single step to move to any one of eight adjacent lattice points (up, down, left, right, or diagonally in any direction).

Each one of Mirko's friends also lives at some lattice point (x, y), and is willing to walk some distance to meet him. Specifically, Mirko will meet a given friend at some lattice point with distance of at most P steps from this friend's house, with P depending on the specific friend's laziness.

After finishing his stroll, Mirko has recalled the order in which he has met with his friends. Compute the minimum possible number of steps that Mirko had to make during his stroll. Mirko's starting and ending position are not known.

입력

• The first line of input contains the positive integer N (2 ≤ N ≤ 200 000), the number of Mirko's friends.
• Each of the following N lines contains three integers describing one friend: x, y, and P (0 ≤ x, y, P ≤ 200 000). Friends are given in the order in which Mirko has met them.

출력

입출력 예

입력

3
3 10 2
8 4 2
2 5 2

출력

4

입력

4
3 3 5
7 11 5
20 8 10
30 18 3

출력

19

First sample description: Mirko could have started his stroll at coordinates (4, 8), met the first friend, taken two steps to the point (6, 6), met the second friend, taken two steps to the point (4, 5) and met the third friend there.

출처:coci 2012