Minimum Ticket Delivery Steps

Mirko needs to deliver tickets to his friends. Each friend’s house is represented as a point ((x,y)) on an infinite 2D grid. When delivering a ticket, the friend can step out of his house and meet Mirko at any grid point that is within (P) moves from his house. Similarly, Mirko moves on the grid by taking one step in any of the eight directions (up, down, left, right, and the four diagonals) per move. Note that under these moves the distance between two points ((x_1,y_1)) and ((x_2,y_2)) is given by the Chebyshev distance, i.e.,

[ d((x_1,y_1),(x_2,y_2)) = \max\left(|x_1-x_2|,|y_1-y_2|\right). ]

For a friend located at ((x,y)) with range (P), the meeting can take place at any point ((u,v)) satisfying

[ \max(|u-x|,|v-y|) \le P. ]

When Mirko goes to deliver all the tickets, he is free to choose the order in which he meets his friends and is also free to choose his starting and ending positions. For two friends with coordinates ((x_1,y_1)) with range (P_1) and ((x_2,y_2)) with range (P_2), the minimum number of steps Mirko needs to travel between their meeting zones is

[ \text{cost} = \max\Bigl(\max\bigl(0, |x_1-x_2| - (P_1+P_2)\bigr),; \max\bigl(0, |y_1-y_2| - (P_1+P_2)\bigr)\Bigr). ]

Your task is to compute the minimum total number of steps that Mirko must move in order to deliver tickets to all his friends.

inputFormat

The first line of the input contains an integer n (1 ≤ n ≤ 15), the number of friends.

Then follow n lines. Each of these lines contains three integers x, y, and P (-10^9 ≤ x,y ≤ 10^9 and 0 ≤ P ≤ 10^9), representing the coordinates of the friend’s house and the maximum number of steps the friend can move to meet Mirko.

outputFormat

Output a single integer: the minimum number of steps Mirko must move in order to deliver all the tickets.

sample

1
0 0 0

0