Meetings

This summer, Jonghyuk plans to go to a rock festival with his friends. He bought all of his friends' tickets himself, and now he wants to deliver the tickets to them.

The village where Jonghyuk and his friends live can be represented as a two-dimensional plane. Jonghyuk can stand only on integer coordinates. In one step, he may move to one of the eight neighboring coordinates: up, down, left, right, or diagonally.

Each friend can walk a little away from home to receive the ticket. If a friend's home is at (x, y) and that friend's value is P, then the friend can meet Jonghyuk at any integer coordinate that is at most P steps away from home. The value P may be different for each friend.

After delivering all tickets, Jonghyuk remembered the order in which he met his friends. Given that order, find the minimum possible number of steps Jonghyuk had to walk. The coordinates where he started and finished the delivery are unknown.

The first line contains the number of friends N. (2 <= N <= 200,000)

Each of the next N lines contains a friend's home coordinates x, y, and value P. (0 <= x, y, P <= 200,000)

The friends are given in the order Jonghyuk met them while delivering the tickets.

Print the minimum number of steps Jonghyuk needs to deliver all tickets.

In the first visible test, Jonghyuk can start the delivery at (4, 8) and meet the first friend there. Then he can move to (6, 6) to meet the second friend, and to (4, 5) to meet the third friend.