Mirko is taking all his friends to a Zaz concert soon to be held in Zagreb. He has already obtained the tickets, and is now walking around the neighbourhood delivering them to everyone.

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.

Input Specification

The first line of input contains the positive integer ~N~ ~(2 \le N \le 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 \le x, y, P \le 200\,000)~. Friends are given in the order in which Mirko has met them.

Output Specification

The first and only line of output must contain the required minimum possible number of steps that Mirko had to make.

Scoring

In test data worth a total of ~30~ points, all numbers in the input (including ~N~) will be at most ~200~.

In test data worth an additional ~30~ points, no friend will have ~P~ greater than ~10~.

Sample Input 1

3
3 10 2
8 4 2
2 5 2

Sample Output 1

4

Explanation for Sample Output 1

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.

Sample Input 2

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

Sample Output 2

19