Problem Background

Mirko needs to distribute concert tickets to his friends.

Problem Description

The homes of his friends can be represented as points on a two-dimensional grid. Mirko can move in eight directions, always to integer coordinates. He can move one step at a time in the directions up, down, left, right, and the four diagonal directions.

Each friend's home is represented by a point \((x, y)\) on the plane. When Mirko arrives at a friend's home to deliver a ticket, the friend can also come out to meet him, moving in any of the eight directions. Therefore, Mirko and this friend can meet at a position up to \(P\) steps away from the friend's home. \(P\) varies for each friend.

Mirko's starting and ending positions are unknown.

Determine the minimum number of steps Mirko must take to deliver all the tickets.

Input Format

The first line contains an integer \(N (2 \leq N \leq 200{,}000)\), representing the number of friends Mirko has.

The next \(N\) lines each contain three numbers \(x, y, P (0 \leq x, y, P \leq 200{,}000)\). These represent the coordinates \((x, y)\) and the parameter \(P\) for each friend, given in the order Mirko delivers the tickets.

Output Format

Output a single integer, which is the minimum number of steps Mirko must take.

Sample Input and Output

Sample Input #1

3
3 10 2
8 4 2
2 5 2

Sample Output #1

4

Sample Input #2

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

Sample Output #2

19

Notes

For all data, it is guaranteed that \(2 \leq N \leq 200{,}000\) and \(0 \leq x, y, P \leq 200{,}000\).

见题面 Input 部分

见题面 Output 部分